快速幂
快速幂
用于快速（在 \(O(\log k)\) 的时间复杂度之内）求出 \(a^k \bmod p\) 的结果，\(1 \le a,p,k \le 10^9\)，核心是反复平方法。
算法思想：
- 预处理出这些值： \(a^{2^0} \bmod p,a^{2^1} \bmod p,a^{2^2} \bmod p,\cdots ,a^{2^{\log k}} \bmod p\)（共 \(\log k\) 个）\[\begin{aligned} a^{2^0} &= a\\ a^{2^1} &= (a^{2^0})^2\\ a^{2^2} &= (a^{2^1})^2\\ &\cdots\\ a^{2^{\log k}} &= (a^{2^{\log k - 1}})^2 \end{aligned} \]
- 若要求得 \(a^k\)，则我们首先将 \(a^k\) 拆分为预处理出的若干个值的乘积的形式，即：\[a^k = a^{2^{x_1}} \cdot a^{2^{x_2}} \cdots a^{2^{x_t}} = a^{2^{x_1} + 2^{x_2} + \cdots + 2^{x_t}} \]于是将问题转化为将 \(k\) 拆分为 \(2^0, 2^1, \cdots , 2^{\log k}\) 中若干个数的和，将 \(k\) 化为二进制即可。\[\begin{aligned} & k = (110110)_2 \\ & k = 2^5 + 2^4 + 2^2 + 2^1 \end{aligned} \]
时间复杂度：\(O(N\log k)\)
#include <iostream>
using namespace std;
typedef long long LL;
LL quick_mi(int a, int k, int p)
{
LL res = 1;
// k=0时跳出循环
while (k) {
// 如果k的个位是1，则将对应的预处理值算入乘积（a是动态变化的）
if (k & 1) res = (LL)res * a % p;
// 当前个位处理结束，右移一位
k >>= 1;
// 更新a的值
a = (LL)a * a % p;
}
return res;
}
int main()
{
int n;
scanf("%d", &n);
while (n -- ) {
int a, k, p;
scanf("%d%d%d",&a, &k, &p);
printf("%d\n", quick_mi(a, k, p));
}
return 0;
}
快速幂求逆元
乘法逆元
若整数 \(b, m\) 互质，并且 \(b|a\) ，则存在一个整数 \(x\) ，使得 \(a/b \equiv a * x \pmod m\) 。称 \(x\) 为 \(b\) 的模 \(m\) 乘法逆元，记为 \(b^{-1}\pmod m\) 。
因为 \(a/b \equiv a * b^{-1} \equiv a/b * b * b^{-1} \pmod m\) ，所以 \(b * b^{-1} \equiv 1 \pmod m\) 。
如果 \(m\) 是质数（此时用 \(p\) 代替 \(m\) ）并且 \(b<p\) ，根据费马小定理， \(b^{p-1} \equiv 1 \pmod p\) ，即 \(b * b^{p-2} \equiv 1 \pmod p\) 。因此，当模数 \(p\) 为质数时， \(b^{p-2}\) 即位 \(b\) 的乘法逆元。
如果只是保证 \(b,m\) 互质，那么乘法逆元可通过求解同余方程 \(b*x \equiv 1 \pmod m\) 得到。
如果 \(b\) 和 \(m\) 不互质，即 \(b\) 是 \(m\) 的倍数时，\(b*x \bmod m\) 一定为0，所以一定无解
#include <iostream>
using namespace std;
typedef long long LL;
// 快速幂，返回 a^k % p
LL quick_mi(int a, int k, int p)
{
LL res = 1;
while (k) {
if (k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main()
{
int n;
scanf("%d", &n);
while (n -- ) {
int a, p;
scanf("%d%d", &a, &p);
// 当a时p的倍数时，a * x mod p一定为0，不可能等于1，所以无解
if (a % p == 0) puts("impossible");
// 当模数 p 为质数时，a^{p−2} 即为 a 的乘法逆元
else printf("%d\n", quick_mi(a, p - 2, p));
}
return 0;
}