1. 题目
2. 读题(需要重点注意的东西)
思路:
快速幂的作用
快速地求出a的k次方模上p的结果快速幂的主要思想
预处理出logk个数,然后用这logk个数中的若干个数在O(1)的时间组合出a的k次方模上p的结果。
3. 解法
---------------------------------------------------解法---------------------------------------------------
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p)
{
LL res = 1 % p;
// 求k的二进制数,再用这二进制数求出a的k次方模p的结果
while (b)
{
// 如果当前k的末尾是1
if (b & 1) res = res * a % p;
// 置a的值为a的平方模p
a = a * (LL)a % p;
// 向右移一位
b >>= 1;
}
return res;
}
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
int a, b, p;
scanf("%d%d%d", &a, &b, &p);
printf("%lld\n", qmi(a, b, p));
}
return 0;
}
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- 快速幂
6. 总结
快速幂的模板题,理解公式并背下代码。
图片失效啦答主
为什么a=aa%p不对,而加上(LL)就对了呢,即a=a(LL)a%p?
a * a 爆int了 要转换为long long
牛
为什么预处理的时候预处理的是 a^2^i %p 而不是 a^2^i
因为每一个数都是前一个数的平方%p
LL res = 1 % p;这里为什么要%p呢
这个写不写都行
干净利落
每时每刻都有人刷题啊~~
字写的好好!赞了qwq
谢谢hhh!