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(扩欧)代码,也可以用自带函数