题目描述
给你三个整数 a,b,p，求 a^b mod p。
输入格式
输入只有一行三个整数，分别代表 a,b,p。
输出格式
输出一行一个字符串 a^b mod p=s，其中 a,b,p 分别为题目给定的值， s 为运算结果。
输入输出样例
输入 #1
2 10 9
输出 #1
2^10 mod 9=7
说明/提示
样例解释
2^10 =1024，1024 mod 9=7。
数据规模与约定
对于 100% 的数据，保证 0≤a,b<2^31 ，a+b>0，2≤p<2^31。
解析：
=a*a*…*a，暴力的计算需要O(n)的时间。
快速幂使用二进制拆分和倍增思想，仅需要O(logn)的时间。
对n做二进制拆分，例如，
,对a做平方倍增，例如，
。
n有logn+1个二进制位，我知道了
后，只需要计算logn+1次乘法就可以了。
例如：
quickpow(3,13)
1:(1101)&1=1,res=1*3=3;a=3*3=3^2; n=(110);
2:(110)&1=0; a=3^2*3^2=3^4; n=(11);
3:(11)&1=1,res=3*3^4; a=3^4*3^4=3^8; n=(1);
4:(1)&1=1,res=3*3^4*3^8; a=3^8*3^8=3^16; n=(0);
快速幂可以应用在任何具有结合律的运算中，例如，取模运算、矩阵乘法等。
例如：
(3^13)%p=((3^8)%p*(3^4)%p*(3^1)%p)%p
1. //示例代码 C++ 2. #include <iostream> 3. using namespace std; 4. int a,b,p; 5. int quickpow(long long a,int b,int p){ 6. int res=1; 7. while(b){ 8. if(b&1) res=res*a%p; 9. a=a*a%p; 10. b>>=1; 11. } 12. return res; 13. } 14. int main() 15. { 16. cin>>a>>b>>p; 17. cout<<a<<'^'<<b<<" mod "<<p<<'='<<quickpow(a,b,p)<<endl; 18. return 0; 19. }
1. # 示例代码 Python语言 2. def tobinary(x): 3. t=[] 4. while(x): 5. t.append(x%2) 6. x//=2 7. return t 8. 9. def quickpow(a,b,p): 10. n=tobinary(b) 11. res=1 12. for i in n: 13. if i: 14. res=res*a%p 15. a=a*a%p 16. return res 17. 18. a,b,p=[int(i) for i in input().split()] 19. print("%d^%d mod %d=%d"%(a,b,p,quickpow(a,b,p)))
1. # 其实Python有更简单的写法：在Python中pow()函数本身就可以实现快速幂取模 2. # a,b,p = map(int,input().split()) 3. a,b,p=[int(i) for i in input().split()] 4. print("%d^%d mod %d=%d"%(a,b,p,pow(a,b,p)))
