AcWing 876. 快速幂求逆元
一、什么是逆元？
((a + b)\% p = (a\%p + b\%p) \%p) （对）
((a - b) \% p = (a\%p - b\%p) \%p) （对）
((a * b) \% p = (a\%p * b\%p) \%p) （对）
((a / b) \% p = (a\%p / b\%p) \%p) （错）
为什么除法错的?
证明是对的难，证明错的只要举一个反例:
((100/50)\%20 = 2 ≠ (100\%20) / (50\%20) \%20 = 0)
对于一些题目，我们必须在中间过程中进行求余，否则数字太大，电脑存不下，那如果这个算式中出现除法，会损失精度，导致答案变小。
因为除法在取模运算时没有性质 (( a/b )\% c = (a\%c /b\%c) \%c),这个是不成立的，所以没法计算了，这时数学家提出了个逆元的概念：
比如 (3 /5 mod 7) ,因为(5)在乘法模(7)的世界里的逆元是(3)，所以转化为 (3 * 3 mod 7),就可转化为乘法的性质了，就方便计算了，就是答案(2)。
逆元可以代替除法，除以这个数就等于乘以这个数的逆元。
二、怎么理解逆元的含义？
想像你在一个加法的世界里，以(0)为世界的中心。有一天，你从世界的中心位置，进行了(+3)，突然，你想回到世界的中心，而你只能使用加法，所以你需要找一个数，让你加上这个数后，可以回到(0)这个世界的中心，这个数就是你在加法世界里(3)的逆元，也就是(-3)。
想像你在一个乘法取模(7)的世界里，以(1)为世界的中心，有一天，你从世界的中心位置，进行了(*3 mod 7)的操作，突然，你想回到世界的中心，而你只能使用乘法取模的，所以你需要找到一个数，让你乘上它再模(7)后，回到世界的中心，那么这个数就称为你在乘法模(7)世界的逆元。
举个栗子， (3 * 5 mod 7 =1) 那么(3)和(5)就在乘法(mod7)世界里互为逆元，就像是加法世界里的(3)和(-3)一样。
在这个乘法模(7)的世界里，逆元不是唯一的，比如 (3 * 5 mod 7 =1) 而 (3*9 mod 7 =1)。我们所说的求逆元一般是指逆元当中最小的那个。
三、费马小定理
当(p)为质数时 $large a^{p-1} equiv 1 (mod p) $
⭐️小试牛刀:今天是周一，再过 (3^{2008}) 次方天，是周几呢？
解：因为一周(7)天，其实是在求(3^{2008}\%7)。
此时(p=7),是质数，可以用费马小定理计算同余结果:
计算(2008)与(p-1)的关系，(2008=6*334+4)
所以$3^{2008} equiv 3^{4} (mod quad 7) $ 就是 (81\%7=4)
今天是周一，再过四天就是周五了。
四、怎样求逆元？
-
当(k)为质数时，可以用费马小定理+快速幂求逆元：
(ecause)(a^{p-1}≡1 (modquad p))( herefore)(a imes a^{p-2}≡1 (modquad p))
( herefore) (a^{p-2})就是(a)的逆元。
-
当(n)不是质数时，可以用扩展欧几里得算法求逆元：
(a)有逆元的充要条件是(a)与(p)互质，所以(gcd(a, p) = 1)
假设(a)的逆元为(x)，那么有(a * x ≡ 1 (mod p))
等价：(ax + py = 1)
(exgcd(a, p, x, y))
二、完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
// 快速幂 (a^k)%p
LL qmi(int a, int k, int p) {
LL res = 1;
while (k) {
if (k & 1) res = res * a % p;
a = a * (LL) a % p;
k >>= 1;
}
return res;
}
int main() {
//读入优化
ios::sync_with_stdio(false);
int n;
cin >> n;
while (n--) {
int a, p;
cin >> a >> p;
if (a % p == 0) puts("impossible");//不互质
else printf("%lld
", qmi(a, p - 2, p));
}
return 0;
}