int gcd(int n,int m)//n>m
{
//最大公约数
int r;
while(m)
{
r = n%m;
n = m;
m = r;
}
return n;
}int kgcd(int a,int b)
{
if(!a) return b;
if(!b) return a;
if(!(a&1) && !(b&1))
return kgcd(a>>1,b>>1)<<1;
else if(!(b&1)) return kgcd(a,b>>1);
else if(!(a&1)) return kgcd(a>>1,b);
else return kgcd(abs(a-b),min(a,b));
}//扩展欧几里得
//求方程ax+by+c = 0有多少整数解
int extgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1;
y=0;
return a;
}
int d = extgcd(b,a%b,x,y);
int t = x;
x=y;
y=t-a/b*y;
return d;
}
