博客

斐蜀定理：

若a,b的最大公约数为gcd,则有a*x+b*y , x , y 这三个数都是gcd的因子,存在x,y使得a*x+b*y=gcd成立

特别地，

若a,b两数互质，则一定有a*x+b*y=1,反过来，结论也是成立的

n个正数之间的斐蜀定理：

既可以推广到n个数字，若a1,a2,…,an的最大公约数为gcd,则存在x1,x2,….,xn使得

a1*X1+a2*X2+….+an*Xn=gcd

成立

特别地，若a1,a2,…,an互质（注意是整体互质，而不是两两互质），则一定有a1*X1+a2*X2+…+an*Xn=1成立

对任何整数a、b和它们的最大公约数gcd，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：

ax + by = m有解当切仅当m是gcd的倍数。

裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用扩展欧几里得算法求得一组特解。

【bzoj1441】Min

Description

Input

Output

Sample Input

Sample Output

分析：n个整数的斐蜀定理

代码如下：

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int n,ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	   {int x;scanf("%d",&x);ans=gcd(ans,x);}
	printf("%d",abs(ans));
	return 0;
}