什么是裴蜀定理
裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约 数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。 ——百度百科
用人话来说就是： $\sum a_i*x_i=b$ 上面的x有解当且仅当 $gcd(ai)b$
例题
luogu P4549 【模板】裴蜀定理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int main()
{
int n=read();
int ans;
if(n<2)
ans=read();
else
{
ans=gcd(read(),read());
for(int i=3;i<=n;i++)
ans=gcd(ans,read());
}
printf("%d",ans>0?ans:-ans);
return 0;
}
|
