数论之扩展欧几里德
扩展欧几里德首先要提到的是裴蜀定理:
设 gcd(a,b)=c,则对于任意实数 x,y 有 c|ax+by 成立
特别的,一定存在 x,y 满足 ax+by=c
推论:a,b 互质等价于 ax+by=1 有解。
求解 x,y:
设 a>b。
(1) 当 a mod b =0 时,gcd(a,b)=b。此时 x=0,y=1。
因为 0*a+1*b=b
(2) 当 a mod b!=0 时
设 ax1+by1=gcd(a,b),bx2+(a mod b)y2=gcd(b,a mod b);
据欧几里德原理有:ax1+by1=bx2+(a mod b)y2;
因为 a mod b=a-(a/b)*b;
则有:ax1+by1=bx2+(a-a(a/b)*b)y2
根据恒等原理有: x1=y2,y1=x2-(a/b)*y2;
于是我们便有了代码:
1 #include <cstdio> 2 using namespace std; 3 long long a,b,x,y; 4 5 void exgcd(long long a,long long b,long long &x,long long &y) 6 { 7 if(a%b==0) 8 { 9 x=0;y=1;return ; 10 } 11 exgcd(b,a%b,x,y); 12 long long t=x; 13 x=y;y=t-(a/b)*y; 14 } 15 16 int main() 17 { 18 scanf("%lld%lld",&a,&b); 19 exgcd(a,b,x,y); 20 printf("%lld%lld",x,y); 21 return 0; 22 }
其实,这个代码还有个压缩版本:
1 #include <cstdio> 2 using namespace std; 3 long long a,b,x,y; 4 5 void exgcd(long long a,long long b,long long &x,long long &y) 6 { 7 if(a%b==0) 8 { 9 x=0;y=1;return ; 10 } 11 exgcd(b,a%b,y,x); //注意了, y 在前, x 在后 12 y-=x*(a/b); 13 } 14 15 int main() 16 { 17 scanf("%lld%lld",&a,&b); 18 exgcd(a,b,x,y); 19 printf("%lld%lld",x,y); 20 return 0; 21 }