当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 <iostream>
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 <iostream>
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;
}
说一下我遇到的两个问题：
1. 因为 p 是质数，所以不用写p%a==0，写了反而会错，因为当a=1时，ans应该为1,但是由于p%a==0，会输出impossible
2. 此处还需 mod p 的原因是题目要求输出 0~p-1 的逆元
MARK
（1）当a与p互质时，用快速幂求逆元（费马小定理）：quick_power(a, b, p)；
（2）当a与p不互质时，用扩展欧几里得算法求逆元：exgcd(a, p, x, y)。
好像有问题，讨论的情况应该是p是否为质数
a与p是有逆元的必要条件，讨论的是p是否为质数
欧几里得算法求逆元时，输出时直接＋p再%p，不会有负数吗，是可证明还是数据的原因呢，求大佬指教（笑
我自己去生成了几万组的数据，貌似没有出现负数的(逃
当x为正数时，+p再modp可以保证x再[0,p-1]之间
当x为负数时，+p可以让x变成正数
多谢（思维定式了（笑🤣
所以+p为什么不会负数啊？
1 ≡ b * x (mod n)与 b * x ≡ 1 (mod n)等价吗
我不是很懂啊
是的，同余的性质
写的很好，清晰易懂，简洁优雅。
简洁,明了,感谢!
为什么exgcd这里cout << ((LL)x + p) % p << endl;，x要LL呀
最后d不是是1的倍数都可以吗
判断互质是要a%p==1
orz
当n为质数时，可以用快速幂求逆元： k|a
k / a ≡ k * x (mod p)
两边同乘a可得 k ≡ k *a * x (mod p)
即 1 ≡ a * x (mod p)
同 a * x ≡ 1 (mod p)
由费马小定理可知，当p为质数时
a ^ (p - 1) ≡ 1 (mod p)
拆一个a出来可得 a * a ^ (p - 2) ≡ 1 (mod p)
故当p为质数时，a的乘法逆元 x = b ^ (p - 2)
换成这样就好理解了
想问一下，题目求的不是 逆元吗，为什么最终答案是 逆元再去 mod p
你的意思是最后那个+p modp吗 因为要确保答案是正数
不是噢，我问的快速幂求逆元的，不是扩展欧几里得求逆元的
快速幂最后哪里有mod呢
因为题目要求返回0 ~ p - 1 之间的一个逆元
好证明
好id
哈哈哈
应该是p是不是质数吧 n？ n在这个代码里面不是次数吗
当n不是质数时，用用欧拉函数求小于或等于n的正整数中与n互质的数的数目，然后再用欧拉定理不行嘛？
那样的话时间复杂度就是根号n了吧，扩展欧几里得时间复杂度是logn。
a,p互质应该是gcd(a,p)==1， 而不是a%p，能过应该是数据比较水
因为p是质数，除了p的倍数，p与其他数都互质，所以可以写a%p
哦，对
快速幂那个
不用gcd，你这样写有问题，比如21 18 这组数据
当n为质数时，才能用快速幂求逆元
懂了，谢谢🙏