一段快速幂算法(题源来自洛谷第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中(或者其他的内存处理规则)导致的越界引起错误。
求解错误原因,并希望能获得关于多步计算中数据暂存的完整知识(给个链接文章也可
那就再加个long long t;
t = (long long)a * a;
a = t % p;