include

int quickmin(int a, int b, int c)
{
int sum = 1;
a = a%c;
while (b > 0)
{
if (b & 1)
{
sum = (sum*a) % c;
}
a = (a*a)%c;
b = b / 2;
}
}

int gcd(int a,int b)//欧几里得算法：求a,b的最大公约数
{
while (b != 0)
{
int r = b;
b = a%b;
a = r;
}
return a;
}

long long exgcd(long long a,long long b,long long &x,long long &y)
{
if (b==0) { x=1,y=0; return a; }
long long d=exgcd(b,a%b,x,y);
long long tmp=x;
x=y;
y=tmp-a/b*y;
return d;
}