裴蜀定理和扩展欧几里得定理

裴蜀定理

什么是裴蜀定理

若a，b为整数，且gcd（a，b）=d，那么对于任意的整数 x，y，ax + by 都一定是d的倍数，特别地，一定存在整数x，y，使 a x + b y = d成立。

裴蜀定理证明如下

例题

题目链接

思路

这个题我们可以把A看作系数，把X看作未知量，我们要求S最小正整数解，根据裴蜀定理可得，当S=gcd($A_1$,$A_2$,$A_3$,…$A_n$)

代码

signed main()
{
	IOS
	int T=1;
	//cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		cin>>a[i];
		int t=a[1];
		for(int i=1;i<=n;i++)
		{
			t=__gcd(t,abs(a[i]));
		}
		cout<<t<<endl;
	}
	return 0;
}

扩展欧几里得

什么是扩展欧几里得定理

扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），
使它们满足贝祖等式 ax + by = gcd(a,b)(裴蜀定理)
如果a是负数，可以把问题转化成|a|(-x)+by = gcd(|a|,b) ，然后令x’=(-x)。
通常谈到最大公约数时，我们都会提到一个非常基本的事实：给予二个整数a、b，必存在整数x、y使得ax + by = gcd(a,b)。
有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，而模反元素在RSA加密算法中有举足轻重的地位。

扩展欧几里得证明如下

模板

#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define int long long
#define endl '\n'
#define PII pair<int,int> 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0){
		x=1,y=0;
		return a;
	}
	int x1,y1,d;
	d=exgcd(b,a%b,x1,y1);
	x=y1,y=x1-a/b*y1;
	return d;
}
signed main()
{
	IOS
	int T=1;
	//cin>>T;
	while(T--)
	{
		int x,y;
		int t=exgcd(8,6,x,y);
		cout<<x<<" "<<y<<endl;
	}
	return 0;
}

例题

题目链接

思路

可以把同余方程转换成不定方程，用扩展欧几里得算法求出x，再判断x是否为最小正整数解就行了

代码

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	int x1,y1,d;
	d=exgcd(b,a%b,x1,y1);
	x=y1,y=x1-a/b*y1;
	return d;
}
signed main()
{
	IOS
	int T=1;
	//cin>>T;
	while(T--)
	{
		int x,y,a,b,t;
		cin>>a>>b;
		int d=exgcd(a,b,x,y);
		int q=(x % b + b) % b;;
		cout<<q<<endl;
	}
	return 0;
}