资料链接:例题 详解
//求最大公约数gcd(a,b)
int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}
//最小公倍数lcm(a,b)
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
//扩展欧几里得算法:求线性方程ax+by=gcd(a,b)
int ex_gcd(int a,int b,int& x,int& y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int g=ex_gcd(b,a%b,x,y);//g为最大公约数
int tmp=x;
x=y;
y=tmp-a/b*y;
return g;
}
//若求ax+by=m,m|gcd(a,b),
//先求ax0+by0=gcd(a,b),x=x0*m/gcd(a,b),y=y0......
阅读全文