文章目录
欧几里得算法（辗转相除法）
欧几里得算法是用于求最大公约数
任何一个数a都可以表示成
a=pb+r
如果r=0则b就是其最大公约数
如果r！=0，就转化为b，r的
a,q,p,r均为整数
gcd表示最大公约数
gcd(a,b)=gcd(b,r)=gcd(b,a%b)
因此结束条件就是r=0，即b=0
typedef long long ll;
//最大公约数
int gcd(int a, int b)
{
return b==0?a:gcd(b, a % b);
}
最小公倍数
我们知道a和b的最小公倍数是a和b的乘积除以gcd（a，b）
但是我们如果用两数相乘的话有可能会溢出
//最小公倍数a*b/gcd（a，b），为了避免溢出应该用a/gcd（a，b）*b
int lcm(int a, int b)//
{
return a / gcd(a, b) * b;
}
贝祖定理
ax+by称a，b的线性组合，
ax+by=m有解，当且仅当m为gcd（a，b）的倍数
ax+by=1时，说明a，b互质
如8和12的最大公约数是4
8x+12y=4,x=-1,y=1为其的一组解
扩展欧几里得算法
ll exgcd(ll a, ll b, ll& x, ll& y)//通过计算出gcd求得解
{
if (b == 0ll)
{
//此时ax+by=g
//gcd=a
//x=1,y=0/1/2………任意数
//x=1,y=0为其中的一组解
x = 1;
y = 0;
return a;//到达递归边界开始向上一层返回
}
//gcd（a，b）=gcd(b,a%b)
ll x1=0, y1=0;
ll g = exgcd(b, a % b, x1, y1);//最大公约数,g为最大公约数
//b*x1+(a%b)*y1=gcd(b,a%b)=gcd(a,b);
//(x1,y1)->(x,y)
x = y1;//x等于上一轮的y1
y = x1 - (a / b) * y1;
return g;//g就是最大公约数
}
int main()
{
ll a, b;
while (cin >> a >> b)
{
//先判断是否有解
//（a，b），的最大公约数为1,有解
if (gcd(a, b) != 1ll)//无解，不为互质数
{
cout << "sorry" << endl;
continue;
}
ll x, y;//x和y就是解
//求ax+by的一组解,用引用传就可以把x和y给解出来
ll g = exgcd(a, b, x, y);
//x = (x % b + b) % b;//以正数形式表现
cout <<"x=" << x << " y=" << y << endl;
}
return 0;
}
