exgcd复习 Apare_xzc
exgcd复习
2019/3/25 xzc
拓展欧几里得原理可以用来解这样的不定方程：
aX + bY = c(求X,Y)
若c不是gcd(a,b)的倍数，则该不定方程一定无解
则问题可以转化为求不定方程的一组解{x,y}：
aX + by = gcd(a,b)
我们知道欧几里得算法：gcd(a,b) = gcd(b,a%b)
(1.0). a * X1 + b * Y1 = gcd(a,b)
(2,1). b * X2 + a%b*Y2 = gcd(b,a%b)
(2.2). b*X2 + (a-a/b*b)*Y2 = gcd(b,a%b)
联立(1.0)和(2.2)可得：
a * X1 + b * Y1 = b * X2 + (a-a/b*b)*Y2
化简后，用待定系数法：
a * X1 + b * Y1 = a * Y2 + b * (X2 - a/b*Y2)
可得 :<mark>X1 = Y2 , Y1 = (X2 - a/b*Y2)</mark>
如果递归下去，b==0,则a = gcd
此时方程为：aX+bY = a 则可令x = 1, y = 0
那么要求原始方程的X,Y，我们要回溯回去，即用X2和Y2推回去X1和Y1
令X_1 = Y2, Y_1 = X2
则X1 = X_1，Y1 = Y_1 - (a/b)*Y2
则Y1 = Y_1 - (a/b)*X_1
参考博客:
https://blog.csdn.net/weixin_39645344/article/details/83615901
见代码：
//#define LL long long
void exgcd(LL a,LL b,LL &x,LL &y,LL &d)//d is gcd(a,b)
{
if(b==0)
{
d = a, x = 1,y = 0;
return;
}
exgcd(b,a%b,y,x,d);
y -= (a/b)*x; //回溯
}
那么拓展欧几里得算法除了求这样的不定方程的解还能干什么呢？
还能求乘法逆元！
什么是乘法逆元呢？
如果 a * b % m = 1,则我们称b为a关于模为m的乘法逆元
(a + b) % mod = (a % mod) + (b % mod)
(a - b) % mod = (a % mod) - (b % mod)
(a * b) % mod = (a % mod) * (b % mod)
(a / b) % mod = (a % mod) / (b % mod) <–这是错的！
(a/b) %mod = 1 <=> a * inv(a) %mod = 1
其中inv(a)是a关于mod的乘法逆元。满足a * inv(a) % mod = 1
- 那如何求乘法逆元呢？我们可以用拓展欧几里得算法求解(还可以用 inv(a) = a^p % mod 求,其中p为euler(a)-1,其中euler(x)为欧拉函数，代表小于x的正整数中和x互质的数的个数)
- 我们已经可以用exgcd求得 aX+bY = gcd(a,b)的解了
- 还有一个很明显的结论：若x和mod不互质，则不存在x关于模为mod的乘法逆元
因为假设这样的逆元为y，则有x * y % mod = 1, 令x = p*g, mod = q*g,(p,q互质)，则 x * y % mod = p * g * y % (q * g), 结果为g的倍数，不是1
所以，用exgcd可以求出aX+bY=gcd(a,b)=1的解
设解为X=x0,Y=y0,
则a * x0 = 1 - b * y0
则a * x0 % b = 1
故x0是a关于b的乘法逆元
我们令x = x0,则x是答案，但x可能是负数，我们可以进行下面的操作，是x成为小于b的满足条件的正整数：
x = ( (x % b) + b ) % b;
见代码：
//#define LL long long
LL getInv(LL a,LL mod,LL &g)
{
LL x,y,d;
exgcd(a,mod,x,y,d);
g = d;
return (x%mod+mod)%mod;
}
测试程序:
#include <iostream>
#include <iomanip>
using namespace std;
#define LL long long
void exgcd(LL a,LL b,LL &x,LL &y,LL &d)
{
if(b==0)
{
d = a, x = 1,y = 0;
return;
}
exgcd(b,a%b,y,x,d);
y -= (a/b)*x;
}
LL getInv(LL a,LL mod,LL &g)
{
LL x,y,d;
exgcd(a,mod,x,y,d);
g = d;
return (x%mod+mod)%mod;
}
int main()
{
LL x,mod;
cout<<"求X关于mod的乘法逆元\n请输入X,mod: ";
while(cin>>x>>mod)
{
LL g;
LL inv = getInv(x,mod,g);
if(g!=1)
{
printf("%lld和%lld不互质，没有逆元！\n\n请继续输入X,mod(ctrl z to exit): ",x,mod);
continue;
}
printf("%lld关于%lld的逆元为：%lld\n",x,mod,inv);
printf("%lld * %lld %% %lld = %lld\n\n请继续输入X,mod(ctrl z to exit): ",x,inv,mod,x*inv%mod);
}
return 0;
}
