扬州手机网站开发百度竞价开户联系方式
题目描述
给定 n n n组 a i , b i , p i a_i,b_i,p_i ai,bi,pi，对于每组数据，求出 a i b i m o d p i a_i^{b^i}~mod~p_i aibi mod pi 的值。
样例
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
快速幂解决的问题
用来解决快速的求解 a k m o d a^k~mod ak mod p p p的结果
时间复杂度为 O ( l o g k ) O(logk) O(logk)
原理（反复平方法）
预处理出来这些值：
a 2 0 m o d p a^{2^0}~mod~p a20 mod p
a 2 1 m o d p a^{2^1}~mod~p a21 mod p
a 2 2 m o d p a^{2^2}~mod~p a22 mod p
. . . ... ...
a 2 l o g k m o d p a^{2^{logk}}~mod~p a2logk mod p
大概是logk个
则 a k a^k ak可以表示为前面分解的这些数的某些数的乘积
则 k k k可以表示为 2 2 2的若干次幂的和
（利用k的二进制表示）
a k = a 2 x 1 a 2 x 2 . . . a 2 x t = a 2 x 1 + 2 x 2 + . . . + 2 x t a^k =a^{2^{x_1}}a^{2^{x_2}}...a^{2^{x_t}} =a^{2^{x_1}+2^{x_2}+...+2^{x_t}} ak=a2x1a2x2...a2xt=a2x1+2x2+...+2xt
如何求 a x a^x ax？
a 1 = a a^1~=~a a1 = a
a 2 1 = ( a 1 ) 2 a^{2^1}~=~(a^{1})^2 a21 = (a1)2
a 2 2 = ( a 2 1 ) 2 a^{2^2}~=~(a^{2^1})^2 a22 = (a21)2
. . . ... ...
a 2 l o g k = ( a 2 l o g k − 1 ) 2 a^{2^{logk}}~=~(a^{2^{logk}-1})^2 a2logk = (a2logk−1)2
也就是说，后一个数都是前一个数的平方
也就是经过k次迭代，就可以把这些数分解出来了
其实就是看k的二进制表示里面，哪些位是1，把1对应的这些位对应的数乘起来就可以了
代码
#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;LL qmi(int a, int k, int p){LL res = 1 % p;while(k){if(k & 1) res = res * a % p; //如果最后一位是1，乘上a^2^a%pa = a * (LL)a % p; //a向后迭代，继续平方k >>= 1; //把k的最后以为删掉}return res;
}int main(){int n, a, b, p;cin >> n;while(n--){scanf("%d%d%d", &a, &b, &p);printf("%lld\n", qmi(a, b, p));}return 0;
}
作者：为梦而生
链接：https://www.acwing.com/solution/content/220897/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。