知识整理|数论初步:辗转相除法和扩展欧几里得知识整理|其他

1.辗转相除法虽然很久以前就知道这个方法了，但是一直都不明白原理【汗】
我们假设 G C D ( x , y ) GCD(x,y) GCD(x,y)为x,y的最大公因数，那么有这样的一个结论:
x>=y时： G C D ( x , y ) = G C D ( x m o d y , y ) GCD(x,y)=GCD(x \mod y,y) GCD(x,y)=GCD(xmody,y)（如果x比y小则x mod y还是等于x,不会有影响）
证明如下：
令x，y的最大公因数为n，则 x ∣ n , y ∣ n x|n,y|n x∣n,y∣n， x m o d y x \mod y xmody 等同于x ? y ? k x-y*k x?y?k, 因为 x ∣ n , y ∣ n x|n,y|n x∣n,y∣n所以 x m o d y x \mod y xmody也被n整除，则此时x,y的公因数也是 x m o d y x \mod y xmody，y的公因数，因为n时x，y的最大公因数，所以n也是 x m o d y x \mod y xmody，y的最大公因数。
有了如上这个结论我们就可以愉快地递推了。
但是为什么是“辗转"相除呢，因为这样就能够避免我上面写到的x比y小的问题。我们每次交换x，y的位置，就能让它不停地除下去。
代码如下：

int gcd(int x,int y){ if (y==0) return x; else return gcd(y,x%y); }

扩展欧几里德算法(exgcd) 辗转相除法又被称为欧几里德算法，那么扩展欧几里德算法就是在欧几里德算法上稍加改动得到的。
exgcd用于解决形如 a x + b y = G C D ( a , b ) ax+by=GCD(a,b) ax+by=GCD(a,b)这样的不定方程求特殊根的问题（求出一个特殊根 x 0 , y 0 x0,y0 x0,y0就可以用公式 x = x 0 + b G C D ( a , b ) ? t , y = y 0 ? a G C D ( a , b ) ? t x=x0+\frac b {GCD(a,b)}*t,y=y0- \frac a {GCD(a,b)}*t x=x0+GCD(a,b)b??t,y=y0?GCD(a,b)a??t来求出所有的根）
其实辗转相除法与不定方程有很深的关系：
辗转相除最后的答案必定是 a = G C D ( a , b ) , b = 0 a=GCD(a,b),b=0 a=GCD(a,b),b=0.
带入方程 a x + b y = G C D ( a , b ) ax+by=GCD(a,b) ax+by=GCD(a,b)，可求得x=1，y=0。
那么可以表示为: a ? 1 + b ? 0 = G C D ( a , b ) a*1+b*0=GCD(a,b) a?1+b?0=GCD(a,b)
对于某一个x 1 , y 1 x1,y1 x1,y1,满足： a x 1 + b y 1 = G C D ( a , b ) ax1+by1=GCD(a,b) ax1+by1=GCD(a,b)
那么必定存在另一组x2,y2满足： b ? x 2 + ( a m o d b ） y 2 = G C D ( b , a m o d b ) b*x2+(a \mod b）y2=GCD(b,a\mod b) b?x2+(amodb）y2=GCD(b,amodb)（这一项即为辗转相除法求得的下一项）
由上面的结论: G C D ( x , y ) = G C D ( x m o d y , y ) GCD(x,y)=GCD(x\mod y,y) GCD(x,y)=GCD(xmody,y)
可得： a ? x 1 + b ? y 1 = b ? x 2 + a m o d b y 2 a*x1+b*y1=b*x2+a \mod by2 a?x1+b?y1=b?x2+amodby2
这个等式也可以写成: a ? x 1 + b ? y 1 = b ? x 2 + （ a ? a b ? b ） ? y 2 a*x1+b*y1=b*x2+（a-\frac a b*b）*y2 a?x1+b?y1=b?x2+（a?ba??b）?y2
变形： a ? x 1 + b ? y 1 = a ? y 2 + b ? x 2 ? a b ? b ? y 2 = a ? y 2 + b ? ( x 2 ? a b ? y 2 ) a*x1+b*y1=a*y2+b*x2-\frac a b*b*y2=a*y2+b*(x2-\frac {a} {b}*y2) a?x1+b?y1=a?y2+b?x2?ba??b?y2=a?y2+b?(x2?ba??y2)
那么就可以发现: x 1 = y 2 , y 1 = x 2 ? a b ? y x1=y2,y1=x2-\frac a b*y x1=y2,y1=x2?ba??y。
又因为我们确定了边界（1，0），所以可以递推解决。
代码如下：

void exgcd(int a,int b,int &x,int &y){ if (b==0) {x=1,y=0; return; } exgcd(b,a%b,x,y); int t=x; x=y,y=t-a/b*y; }//x,y就是所求的特殊解

扩展欧几里得算法求线性模方程的最小正整数解 【知识整理|数论初步:辗转相除法和扩展欧几里得】我们先考虑一个线性方程， a x ≡ b ( m o d c ) ax≡b (mod c) ax≡b(modc)。
我们要求这个方程的一个最小正整数解。
那么 b b b一定能够表示成 c k + a x ck+ax ck+ax的形式，因为 a x ax ax和 b b b模 c c c同余。
那么就可以写成一个不定方程： a x + b y = c ax + by = c ax+by=c
这就可以用不定方程求解。
首先如果gcd（a，b)不是c的倍数，那么肯定无解。
否则，我们我们求一下exgcd（a，b）。
考虑通解的一个方程：
设x0，y0为一组特殊解，可知通解为：
x = c g c d ( a , b ) ? x 0 + b g c d ( a , b ) ? t x=\frac c {gcd(a,b)}?x0+\frac b {gcd(a,b)}?t x=gcd(a,b)c??x0+gcd(a,b)b??t
y = c g c d ( a , b ) ? y 0 – a g c d ( a , b ) ? t , t ∈ Z y=\frac c {gcd(a,b)}?y0–\frac a {gcd(a,b)}?t,t∈Z y=gcd(a,b)c??y0–gcd(a,b)a??t,t∈Z
那么根据这一式子，我们可以推出最小的一组正整数解： ( x 0 ? c g c d （ a ， b ） m o d b + b ) m o d b (x0* \frac c {gcd（a，b）}\mod b+b) \mod b (x0?gcd（a，b）c?modb+b)modb
例题：BZOJ1477 青蛙的约会：传送门
代码如下：

#include #include #define ll long long using namespace std; ll x,y,m,n,L,a,b; ll exgcd(ll x,ll y,ll &x0,ll &y0){ if (y==0) {x0=1,y0=0; return x; } ll ret=exgcd(y,x%y,x0,y0); ll t=x0; x0=y0,y0=t-x/y*y0; return ret; } ll solve(ll a,ll b,ll c){ ll x0,y0,g=exgcd(a,b,x0,y0); if (c%g) return -1; x0=x0*c/g; y0=y0*c/g; x0=(x0%b+b)%b; return x0; } int main(){ scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&L); if (solve(n-m,L,x-y)==-1) printf("Impossible\n"); else printf("%lld\n",solve(n-m,L,x-y)); return 0; }

update 2018.7.20 更新了latex公式。