数论---扩展欧几里得算法

文章目录

• 欧几里得算法（辗转相除法）
• 最小公倍数
• 贝祖定理
• 扩展欧几里得算法

欧几里得算法（辗转相除法）

欧几里得算法是用于求最大公约数
任何一个数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;
}