好久没发博客了，总结下今晚学的扩展欧几里得吧
虽然现在也没学会
ax + by = c
扩展欧几里得知道a b c 求x y
求乘法逆元
a*x = 1（mod m）
知道a和m 求x
先复习一下欧几里得求最大公约数吧
inr gcd(int x,int y) { if(y==0) return x; else return gcd(y,x%y); }求 ax + by = c。
int exgcd(int a,int b,int &x,int &y) { if(b==0) { x = 1; y = 0; return a; } int r = exgcd(b,a%b,x,y); int t = x;x = y; y = t - a/b*y; return r; } int main() { int a,b,c,x,y; while(cin>>a>>b>>c){ int d = exgcd(a,b,x,y); if(c%d) printf("-1\n"); int k = c/d; x*=k; y*=k; printf("%d %d\n",x,y); } return 0; }求乘法逆元
int exgcd(int a,int b,int &x,int &y) { if(a==0&&b==0) return -1; if(b==0) { x = 1; y = 0; return a; } int r = exgcd(b,a%b,y,x); y -= a/b*x; return r; } int cal(int a,int m) { int x,y; int gcd=exgcd(a,m,x,y); if(gcd==1) return (x%m+m)%m; return -1; } int main() { int a,m; while(cin>>a>>m){ int n = cal(a,m); cout<<n<<endl; } return 0; }
