问题遇到的现象和发生背景
一段快速幂算法(题源来自洛谷第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中(或者其他的内存处理规则)导致的越界引起错误。
我想要达到的结果
求解错误原因,并希望能获得关于多步计算中数据暂存的完整知识(给个链接文章也可