gcd(a, b)用于求解自然数a,b的最大公约数
int gcd(int a, int b)
{
if (b==) return a;
return gcd(b, a%b);
}
extgcd(a, b, x, y)用于求解方程ax+by = 1的一组解,并返回a,b的最大公约数
int exgcd(int a, int b, int &x, int &y)
{
int d = a;
if (b!=) {
d = exgcd(b, a%b, y, x);
y -= (a/b)*x;
}
else {
x = ; y = ;
}
return d;
}
暂不给出证明过程,有时间再回来补,不过多半是没时间。。。