蛄丶 2022-07-18 22:39 采纳率: 50%
浏览 25
已结题

c++数据暂存规则?

问题遇到的现象和发生背景

一段快速幂算法(题源来自洛谷第1226题)

问题相关代码,请勿粘贴截图
#include <bits/stdc++.h>
using namespace std;

int _power(int a, int b, int p) {
    a = a % p;
    long long ans = a;
    b--;
    while (b != 0) {
        if (b & 1) {ans = (ans * a) % p;} 
        b = b >> 1;
        **a = (a*a) % p;**
    }
    return ans % p;
}

int main() {
    int a, b, p;
    cin >> a >> b >> p;
    printf("%i^%i mod %i=%i",a,b,p,_power(a,b,p));
    return 0;
}

保证a,b均为0~2**31之间的整数,p在int范围内

运行结果及报错内容

当ab逼近上限时,答案恒为0

我的解答思路和尝试过的方法

0明显是由于数据越界引起的错误,将_power函数内的a定义为long long能保证正常输出。本人猜测可能是由于在a = (a*a) % p一步中,乘方数据暂存到a中(或者其他的内存处理规则)导致的越界引起错误。

我想要达到的结果

求解错误原因,并希望能获得关于多步计算中数据暂存的完整知识(给个链接文章也可

  • 写回答

1条回答 默认 最新

  • 浪客 2022-07-19 10:12
    关注

    那就再加个long long t;
    t = (long long)a * a;
    a = t % p;

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 7月27日
  • 已采纳回答 7月19日
  • 创建了问题 7月18日

悬赏问题

  • ¥100 set_link_state
  • ¥15 虚幻5 UE美术毛发渲染
  • ¥15 CVRP 图论 物流运输优化
  • ¥15 Tableau online 嵌入ppt失败
  • ¥100 支付宝网页转账系统不识别账号
  • ¥15 基于单片机的靶位控制系统
  • ¥15 真我手机蓝牙传输进度消息被关闭了,怎么打开?(关键词-消息通知)
  • ¥15 装 pytorch 的时候出了好多问题,遇到这种情况怎么处理?
  • ¥20 IOS游览器某宝手机网页版自动立即购买JavaScript脚本
  • ¥15 手机接入宽带网线,如何释放宽带全部速度