裴枢定理的简单证明及其推广(Logu P4549)
最编程
2024-07-18 22:32:22
...
题目传送门
裴蜀定理
所谓裴蜀定理,即对于两个正整数x,y,若ax+by=c,则c%gcd(x,y)==0。
证明
令s=gcd(x,y),那么x%s== 0,y%s== 0,当然有ax%s== 0,by%s== 0,所以c%s==0。
如果是三个正整数x,y,z,那么ax+by+dz=c,同理 c%gcd(x,y,z)==0。
推广
由两个数推广到多个数,最后得到的结果一定是这多个数的gcd的倍数。
提示
链接题目中输入有负数,需要把它变成正整数再求gcd。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int inf=0x7fffffff;
const int mod=1e9+7;
const int eps=1e-6;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
//#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
int a[N];
signed main()
{
IOS;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=abs(a[i]);
}
int res=a[1];
for(int i=2;i<=n;i++)
{
res=__gcd(res,a[i]);
}
cout<<res<<endl;
}
上一篇: 贝祖公式简介
下一篇: 数学知识--佩苏定理