代码
#include <iostream>
using namespace std;
typedef long long LL;
int quick_pow(int a, int k, int p)
{
int res = 1 % p;
while (k) {
if (k & 1) {
res = (LL)res * a % p;
}
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
int n;
int main()
{
cin >> n;
while (n--) {
int a, k, p;
cin >> a >> k >> p;
cout << quick_pow(a, k, p) << endl;
}
return 0;
}
你好，请问为什么需要在每一步计算res和a时对p取余，而不是计算完res后再取余呢？
会溢出
明白了，感谢
我想问一下为什么a*a%p不会影响最后的答案，比如2的4次方是16，16%3=1，2的（4%3）次方是2，2%3=2，答案就变了
4的二进制是100，while里面会循环三次，第一次过后，res不变，a=2 * 2%3=1,第二次过后，res不变，a=1 * 1%3=1,第三次过后，res=1 * 1%3=1，a=1 * 1%3=1,答案没有错！
博主你好，a = (LL)a * a % p; 这一段代码还是不太清楚为什么 a*a 可以先对p求模，不会影响最后的答案吗？
因为他有一个数学公式(ab)%c=((a%c)(b%c))%c,就是先算出最后的结果在求模跟先把最后结果的因子求模相乘得出一个结果再最后取一次模的结果是一样的,我这样说不知道你能不能理解
算法进阶指南 YYDS
这个太棒了
res = (LL)res * a % p;, 你写错了
已修正， 感谢！
这是哪本书啊
算法竞赛进阶指南
，这题解，爱了爱了。