快速幂
快速幂:快速求a^b % p的问题,时间复杂度:O(logb)O(logb),若对于n组数据,那么时间复杂度为O(n∗logb)
暴力做法
分析
- 时间复杂度：O(n * b)
- TLE
AC代码
#include <iostream>
using namespace std;
typedef long long LL;
int m;
int main()
{
cin >> m;
while (m -- )
{
int a, b, p;
cin >> a >> b >> p;
LL res = 1;
while (b --)
{
res = res * a % p;
}
cout << res << endl;
}
return 0;
}
快速幂迭代法
分析
时间复杂度：O(n * logb)
AC代码
#include <iostream>
using namespace std;
typedef long long LL;
int m;
LL qmi(LL a, int b, int p)
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
int main()
{
cin >> m;
while(m --)
{
LL a;
int b, p;
cin >> a >> b >> p;
LL res = qmi(a, b, p);
cout << res << endl;
}
return 0;
}
快速幂递归版
分析
时间复杂度：O(n * logb)
AC代码
#include <iostream>
using namespace std;
typedef long long LL;
int m;
LL qmi(LL a, int b, int p)
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
int main()
{
cin >> m;
while(m --)
{
LL a;
int b, p;
cin >> a >> b >> p;
LL res = qmi(a, b, p);
cout << res << endl;
}
return 0;
}
【快速幂】求逆元
题目
https://www.acwing.com/problem/content/878/
思路
当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)
AC代码
#include <iostream>
using namespace std;
typedef long long LL;
int m;
LL qmi(LL a, int b, int p)
{
int res = 1;
while(b)
{
if(b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
int main()
{
int m;
cin >> m;
while (m -- )
{
int a, p;
cin >> a >> p;
int res = qmi(a, p - 2, p);
if(a % p) cout << res << endl;
else cout << "impossible" << endl;
}
return 0;
}
