做网站时空间的选择,网站设计与制作软件,网站仿制可用于商业吗,金属材料东莞网站建设题目描述
给定 n n n组 a i , b i , p i a_i,b_i,p_i ai,bi,pi#xff0c;对于每组数据#xff0c;求出 a i b i m o d p i a_i^{b^i}~mod~p_i aibi mod pi 的值。
样例
输入样例#xff1a;
2
3 2 5
4 3 9输出样例#xff1a;
4
1快速幂解决的问题
用来…题目描述
给定 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}} aka2x1a2x2...a2xta2x12x2...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对应的这些位对应的数乘起来就可以了 代码
#includeiostream
#includealgorithm
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 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
