int gcd(int x,int y){ if(y==0) return x; return gcd(y,x%y); } int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1,y=0; return a; } int m=gcd(b,a%b,x,y),x0=x,y0=y; x=y0; y=x0-(a/b)*y0; return m; } gcd和exgcd(扩欧)代码,也可以用自带函数