裴蜀定理

news/发布时间2024/8/25 20:19:49

定义

设 \(a,b\) 是不全为 \(0\) 的整数

1.对任意整数 \(x,y\)，满足 \(\gcd(a,b)|ax+by\)

2.存在整数 \(x,y\) 使得 \(ax+by=\gcd(a,b)\)

证明

第一条

理解一下即可，比较好理解

第二条

若任何一个等于 \(0\)，则 \(\gcd(a,b)=a\)，这时定理显然成立
若 \(a,b\) 均不等于 \(0\)

由于 \(\gcd(a,b)=\gcd(a,-b)\)，不妨设 \(a,b\) 均 \(>0，a\geq b\)，\(d=\gcd(a,b)\)

对于 \(ax+by=d\)，两边同时 \(\div d\)，可得 \(a_1x+b_1y=1\)，由于除以了 \(a,b\) 的最大公约数，所以此时 \(a,b\) 互质，转证 \(a_1x+b_1y=d\)

回顾 \(exgcd\) 中辗转相除的思想：

\(\gcd(a,b)→\gcd(b,a\bmod b)→…\)，将模出来的数称作 \(r\)，则：

\[\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=…=\gcd(r_{n-1},r_n)=1 \]
将上述式子转换为带余数的除法

\[a_1=q_1b_1+r_1 \]
\[b_1=q_2r_1+r_2 \]
\[r_1=q_3r_2+r_3 \]
\[… \]
\[r_{n-3}=q_{n-1}r_{n-2}+r_{n-1} \]
\[r_{n-2}=q_{n}r_{n-1}+r_n \]
\[r_{n-1}=q_{n+1}r_n \]
当辗转相除法除到互质时，\(r_n=1\)，以 \(x\) 替换 \(q\)，则有：

\[r_{n-2}=x_nr_{n-1}+1 \]
\[→1=r_{n-2}-x_nr_{n-1} \]
将倒数第三个式子转化为 \(r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}\)，代入上式

\[1=r_{n-2}-x_n(r_{n-3}-x_{n-1}r_{n-2}) \]
\[→1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3} \]
然后通过同样方法消去 \(r_{n-2},…,r_1\)

可证得 \(1=a_1x+b_1y\) 是一般式中 \(d=1\) 的情况

同时乘以 \(d\)，得 \(ax+by=d\)

推广

逆定理

若 \(a,b\) 是不全为 \(0\) 的整数，\(d>0\) 是 \(a,b\) 的公因数，且存在整数 \(x,y\)，使得 \(ax+by=d\) 成立，则 \(d=\gcd(a,b)\)

特殊的，当上述的 \(d=1\) 时，则 \(a,b\) 互质

多个整数

\(n\) 个整数的情形：设 \(a_1,a_2,…,a_n\) 是不全为 \(0\) 的整数，则存在整数 \(x_1,x_2,…,x_n\) ，使得 \(\sum\limits_{i=1}^{n}d_ia_i=\gcd(a_1,a_2,…,a_n)\)

其逆定理也成立：设\(a_1,a_2,…,a_n\) 是不全为 \(0\) 的整数，\(d>0\) 是她们的公因数，若存在整数 \(x_1,x_2,…,x_n\)，使得 \(\sum\limits_{i=1}^{n}d_ia_i=\gcd(a_1,a_2,…,a_n)\)，则 \(d=\gcd(a_1,a_2,…,a_n)\)

例题：

\(\Large{Border}\) \((vjudge)\)

简化题意：

给定序列 \(a\)，求满足 \(r=(\sum\limits_{i=1}^{n}d_ia_i)\bmod k\) 的 \(r\) 的个数和所有情况

解法

根据上述证明的裴蜀定理，得到序列 \(x\) 满足 \(\sum\limits_{i=1}^{n}x_ia_i=\gcd(a_1,a_2,…,a_n)\)，且 \(\gcd(a_1,a_2,…,a_n)|\sum\limits_{i=1}^{n}x_ia_i\)

设 \(d=\gcd(a_1,a_2,…,a_n)\),于是设 \(\sum\limits_{i=1}^{n}x_ia_i=dl=kh+r\)

建立一个不定方程 \(dl=kh+r\)，移项得 \(dl-kh=r\)，用 \(x\) 替换 \(l\)，\(y\) 替换 \(-h\)，得到 \(dx+ky=r\)

根据裴蜀定理，方程有解当且仅当 \(\gcd(d,k)|r\)

于是得出 \(exgcd\) 的模型 \(dx+ky=r\)，\(\gcd(d,k)|r\)，根据 \(exgcd\) 的推理过程，当最后一层时 \(x_n=0，y_n=1\)，此时 \(r\) 最大，\(r=k\)

故此，在满足 \(\gcd(d,k)|r\) 的条件下，\(r\) 可以从 \(0\) 取到 \(k\)（每次+ \(\gcd(d,k)\)）

所以共有 \(\dfrac{k}{\gcd(d,k)}\) 个满足的 \(r\)，依次从 \(0\) 输出到 \(k\)（每次+ \(\gcd(d,k)\)）即可，也就是第 \(i(1\leq i\leq \dfrac{k}{\gcd(d,k)})\) 个解为 \((i-1)\times \gcd(d,k)\)

代码如下

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
template<typename Tp> inline void read(Tp&x)
{x=0;register bool z=1;register char c=getchar();for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);x=(z?x:~x+1);
}
int a,n,k,ans;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
signed main()
{#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifread(n),read(k);ans=k;//此处注意！for(int i=1;i<=n;i++)read(a),ans=gcd(ans,a);cout<<k/ans<<endl;for(int i=0;i<k/ans;i++)cout<<i*ans<<' ';
}