裴蜀定理内容:
${ax+by=c,x\in Z^*,y\in Z^*}$成立的充要条件是${\gcd(a,b)|c}$。$Z^*$表示正整数集。
设${s=\gcd(a,b)}$,显然${s|a}$,并且${s|b}$
又因为${x,y\in Z^*}$
所以${s|ax,s|by}$
显然要使得之前的式子成立,则必须满足$c$是$a$和$b$的公约数的倍数
又因为$x$和$y$是正整数
所以$c$必然是$a,b$最大公约数的倍数。
裴蜀定理推广: 若两个素数互素,那么设分别为 $x y$ 那么有 $ax+by=N$,$N$为任何数,也就是若两个数互素,那么他们可以组合成任何数
//【模板】裴蜀定理 //https://www.luogu.com.cn/problem/P4549 #include <bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10,mod=1e9+7; signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,res=1; cin>>n; vector<int>a(n+1); cin>>a[1]; for(int i=2;i<=n;i++) cin>>a[i],res=__gcd(a[i],res); cout<<res<<endl; return 0; }
标签:gcd,数论,res,定理,int,ax,裴蜀 From: https://www.cnblogs.com/o-Sakurajimamai-o/p/18045385