扩展欧几里得能求出形如a*x+b*y=gcd(a,b)的通解x,y。
我们设
a1*x1+b1*y1=gcd(a,b) (1)
a2*x2+b2*y2=gcd(a,b) (2)
并且a2=b1,b2=a1%b1=a1-(a1/b1*b1)
则(1)(2)相等可得a1*x2+b1*y1=b1*x2+[a1-(a1/b1*b1)]* y2
对应系数相等可得:x1=y2 ,y1=x2-a1/b1*y2;
如此迭代下去直到b=0时,有x=1,y=0; (此时gcd(a,b)即为a (n).)
递归往上赋值即可。
代码如下:
LL exgcd(LL a,LL b,LL &x,LL &y) { int d=a; //d记录gcd if(b!=0) { d=exgcd(b,a%b,x,y);//下一步迭代 int t=x; //t记录x x=y; //上一步的x等于下一步的y y=t-a/b*y; //上一步的y等于下一步的x(t)减去a/b*(下一步的y) (此时a,b是上一步的) } else x=1,y=0; //迭代终点 return d; }
假设我们已经求出了a*x+b*y=gcd(a,b)的一组特解x0,y0;
设x,y为通解,x=x0+p,y=y0+q;
带入方程得a*(x0+p)+b*(y0+q)=c,化简得a*p+b*q=0 (因为a*x0+b*y0==c,消去了)
由于p,q为整数先设p=b,q=-a;
由于我们求出了gcd(a,b) ,那么p=b/gcd(a,b) ,q=-a/gcd(a,b) //那么此时p,q一定为最简整数
由于我们找的是通解,则p=b/gcd(a,b)*t,q=-a/gcd(a,b)*t //t为任意整数
那么通解:
x=x0+b/gcd(a,b)*t;
y=y0-a/gcd(a,b)*t;(t为任意整数)(很多博客上都没有解释这通解是怎么来的,还是自己写篇博客记录下吧)
我们现在要求a*x+b*y=c的通解只需将a*x+b*y=gcd(a,b)的通解都乘上c/gcd(a,b)即可。
我们先找到一组特解:x1=x0*c/gcd(a,b) ,y1=y0*c/gcd(a,b);
则a*x+b*y=c的通解:
x=x1+b/gcd(a,b)*t;
y=y1-a/gcd(a,b)*t; (t为任意整数)
那么我们求最小x时只需将对a*x+b*y=gcd(a,b)求出的特解x,y进行如下操作即可
x=x*c/gcd(a,b)
b=b/gcd(a,b)
if(b<0),b=-b;
x=x%b; // 保证x最小
if(x<=0)//根据题目要求,大部分是最小正整数解,如果解可以为0得话,这里去掉0即可。
x+=b; //此时t=1(即多加了1个b(这时的b已经除过了gcd(a,b)))
则此时的x即为最小值。若同时需要求y的话,直接根据此时得x求出即可。
由 a*x+b*y=c
得y=(c-a*x)/b;
代码如下:
void cal(LL a,LL b,LL c) { LL x,y; LL gcd=exgcd(a,b,x,y); if(c%gcd) //如果gcd不是c的因子的话,就不可能相遇 cout<<"Impossible"<<endl; else { x*=c/gcd; //化为a*x+b*y=c模型 b/=gcd; if(b<0) b=-b; LL ans=x%b; if(ans<=0) ans+=b; cout<<ans<<endl; } }
二:乘法逆元:
解法1:扩展欧几里得:由a*x=1(mod p). 由同余性质得 a*x+k*p=1,这即为扩欧形式,直接扩欧求就好了。
解法2:费马小定理:假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p),即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。
那么a*(a^(p-2))=1(mod p).即a^(p-2)为a在mod p下的逆元。而a^(p-2)可以用快速幂求得。这种方法限制较多,使用时要密切注意。
解法3:线性递推:我们用inv[i]代表i在mod p下的逆元,(注意线性递推只能求1~p之间的逆元!)
易知:inv[1]=1,设p=k*i+r . 此时k=p/i(整数下的除法),r=p%i。
上式可化为k*i+r=0(mod p);
上式两边同时乘以inv[i],inv[r]得:k*inv[r]+inv[i]=0(mod p);
则inv[i]=-k*inv[r]=-(p/i)*inv[p%i]%p;
为了保证其为非负得:
得:inv[i]=(p-p/i)*inv[p%i]%p;
解法4:阶乘递推:我们用c[i]代表 i 的阶乘。用f[i]代表i !的逆元。
由 f[i]=1/(i !) (mod p) . f[i+1]=1/(i+1!)(mod p).
得f[i]=f[i+1]*(i+1) (mod p).
由 inv[i]=1/i(mod p).
得 inv[i]=1/(i !)*(i-1)!(mod p).