定义
设 \(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<<' ';
}
注意事项
可见代码中的一行 \(ans\) 初始化为 \(k\),已证 \(ans\) 必为 \(\gcd(d,k)\) 的整数倍数,否则方程无解,若没了这条,显然无法保证 \(ans\) 与这个 \(\gcd\) 中的 \(k\) 去满足