快速幂:快速求abab % p的问题,时间复杂度:O(logb)O(logb),若对于n组数据,那么时间复杂度为O(n∗logb)O(n∗logb)
一.暴力解法 O(n∗b)会TLEO(n∗b)会TLE
基本思路:对于n组数据,分别循环b次求出abmodpabmodp
#include using namespace std; int main() { int n; cin>>n; while(n–) { int a,b,p; long long res=1; cin>>a>>b>>p; while(b–) res = res * a %p; cout<<res<<endl; } }
二.快速幂解法 O(n∗logb)O(n∗logb)
基本思路:
预处理出a20,a21,a22,…,a2logb.这b个数a20,a21,a22,…,a2logb.这b个数
将ab用a20,a21,a22,…,a2logb这b种数来组合,即组合成ab=a2x1×a2x2×…×a2xt=a2x1+2x2+…+2xtab用a20,a21,a22,…,a2logb这b种数来组合,即组合成ab=a2x1×a2x2×…×a2xt=a2x1+2x2+…+2xt即用二进制表示
为什么b可用a20,a21,a22,…,a2logb这b个数来表示?a20,a21,a22,…,a2logb这b个数来表示?∵二进制可以表示所有数,且用单一用二进制表示时,b单一表示最大可表示为二进制形式的2logb二进制可以表示所有数,且用单一用二进制表示时,b单一表示最大可表示为二进制形式的2logb
注意:
b&1就是判断b的二进制表示中第0位上的数是否为1,若为1,b&1=true,反之b&1=false 还不理解?进传送门
b&1也可以用来判断奇数和偶数,b&1=true时为奇数,反之b&1=false时为偶数
快速幂之迭代版 O(n∗logb)O(n∗logb)
#include using namespace std; long long qmi(long long a,int b,int p) { long long res=1; while(b)//对b进行二进制化,从低位到高位 { //如果b的二进制表示的第0位为1,则乘上当前的a if(b&1) res = res a %p; //b右移一位 b>>=1; //更新a,a依次为a{20},a{21},a{22},…,a{2logb} a=aa%p; } return res; } int main() { int n; cin>>n; while(n–) { cin.tie(0); ios::sync_with_stdio(false); int a,b,p; long long res=1; cin>>a>>b>>p; res = qmi(a,b,p); cout<<res<<endl; } return 0; } 快速幂之递归版 O(n∗logb)O(n∗logb) #include using namespace std; #define ull unsigned long long ull quick_pow(ull a,ull b,ull p) { if(b==0) return 1; a%=p; ull res=quick_pow(a,b>>1,p); if(b&1) return resres%pa%p; return res*res%p; } int main() { int n; cin>>n; while(n–) { int a,b,p; cin.tie(0); ios::sync_with_stdio(false); cin>>a>>b>>p; cout<<quick_pow(a,b,p)<<endl; } return 0; }
当n为质数时，可以用快速幂求逆元：
a / b ≡ a * x (mod n)
两边同乘b可得 a ≡ a * b * x (mod n)
即 1 ≡ b * x (mod n)
同 b * x ≡ 1 (mod n)
由费马小定理可知，当n为质数时
b ^ (n - 1) ≡ 1 (mod n)
拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n)
故当n为质数时，b的乘法逆元 x = b ^ (n - 2)
当n不是质数时，可以用扩展欧几里得算法求逆元：
a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1
假设a的逆元为x，那么有a * x ≡ 1 (mod p)
等价：ax + py = 1
exgcd(a, p, x, y)
快速幂求逆元
#include using namespace std; typedef long long LL; LL qmi(int a, int b, int p) { LL res = 1; while(b){ if(b & 1) res = res * a % p; a = (LL)a * a % p; b >>= 1; } return res; } int main() { int n; cin >> n; while(n --){ int a, p; cin >> a >> p; if(a % p == 0) puts(“impossible”); else cout << qmi(a, p - 2, p) << endl; } return 0; } 扩展欧几里得算法求逆元 #include using namespace std; typedef long long LL; int n; int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int main() { cin >> n; while (n --) { int a, p, x, y; // if (a < p) swap(a, p); cin >> a >> p; int d = exgcd(a, p, x, y); if (d == 1) cout << ((LL)x + p) % p << endl;//保证x是正数 else puts(“impossible”);
} return 0;
}
![[解题报告]《算法零基础100讲》(第15讲) 二分快速幂](https://ucc.alicdn.com/pic/developer-ecology/61592505aaa24996944148b4c05f8bb4.png?x-oss-process=image/resize,h_160,m_lfit)