前言
在学习本节内容前，最好先学习同余的基本性质以加深理解。
一堆定理
- 定理1：
若
\[a,b,m,n \in \mathbb Z,c \mid a,c \mid b \]则
\[c \mid (ma+nb) \]证明：
令 \(a=ce,b=cf\) ，
代入 \(ma+nb\) 再提公因式即可。
- 定理2：
若
\[a,b,c \in \mathbb Z \]则
\[(a+cb,b)=(a,b) \]证明：
由定理1证明二者公因子相同即可。
- 定理3：
两个不全为零的整数 \(a,b\) 的最大公因子是 \(a,b\) 线性组合的最小正整数.
证明：令 \(d\) 是 \(a,b\) 的线性组合中最小的正整数， \(d = ma + nb\) , 其中 \(m,n\) 是整数，我们将证明 \(d \mid a,d \mid b\) 。
由带余除法，得到 \(a=dq+r, 0≤r<d\) 。
由 \(a=dq+r\) 和 \(d=ma+nb\) ，得到 \(r=a-dq=a-q(ma+nb)=(1-qm)a-qnb\) .
这就证明了整数 \(r\) 是 \(a,b\) 的线性组合。因为 \(0 ≤ r < d\) ，而 \(d\) 是 \(a,b\) 的线性组合中最小的正整数，
于是我们得到 \(r=0\) （如果 \(r\) 不是等于 \(0\) ，那意味着 \(r\) 才是所有线性组合中最小的正整数，这与 \(d\) 是所有线性组合中最小的正整数矛盾），因此 \(d \mid a\) ，同理可得， \(d \mid b\) .
我们证明了 \(a,b\) 的线性组合中最小的正整数 \(d\) 是 \(a,b\) 的公因子，剩下要证的是它是 \(a,b\) 的最大公因子，为此只需证明 \(a,b\) 所有的公因子都能整除 \(d\) 。
由于 \(d = ma + nb\) ，因此如果 \(c \mid a\) 且 \(c \mid b\) ，那么由定理2有 \(c \mid d\) ，因此 \(d > c\) 。
得证。
- 定理4：
若 \(a,b\) 是正整数，
则所有 \(a,b\) 的线性组合构成的集合与所有 \((a,b)\) 的倍数构成的集合相同。
证明：由定理1得 \(a,b\) 的线性组合都是 \((a,b)\) 倍数。
由定理3得 \((a,b)\) 属于线性组合，其倍数显然也属于线性组合。
得证。
- 定理5：
若
\[a,b,c \in \mathbb Z , m \in \mathbb Z^+ ,d=(c,m) \]且有
\[ac \equiv bc \pmod m \]则
\[a \equiv b \pmod {m/d} \]证明：令 \(ac=km+bc \to (a-b)c=km\)
两边同除 \(d\) 得到：\((a-b)(c/d)=k(m/d)\)
因为 \((c/d)\) 与 \((m/d)\) 互质，
所以有 \((m/d) \mid (a-b)\)
得到结论：\(a \equiv b \pmod {m/d}\)
得证。
- 推论：
若
\[a,b,c \in \mathbb Z , m \in \mathbb Z^+, (c,m)=1 \]且有
\[ac \equiv bc \pmod m \]则有
\[a \equiv b \pmod m \]- 定理6：
若 \(r_1,r_2,…,r_m\) 是一个模 \(m\) 的完全剩余系，且有正整数 \(a\) 满足 \((a,m)=1\)
则对任何整数 \(b\) 有： \(ar_1+b,ar_2+b,…,ar_m+b\) 也是一个模 \(m\) 的完全剩余系。
证明：若有 \(ar_i+b\) 与 \(ar_j+b\) 同余，则有 \(ar_i\) 与 \(ar_j\) 同余。
由定理5推论可得：此时有 \(r_i\) 与 \(r_j\) 同余，矛盾！
故定理成立。
朴素欧几里得定理
若
\[a,b \in \mathbb Z \]则
\[(a,b)=gcd(b,a \% b) \]证明：
令 \(a=bq+r\) ,
得 \(r=a-bq\).
由定理2得，
\(gcd(a,b)=gcd(a-bq,b)=gcd(r,b)=gcd(a\%b,b)=gcd(b,a\%b)\)
扩展欧几里得算法
-
扩展欧几里得算法就是在朴素欧几里得上求一组未知数 \((x,y)\) 的解。
-
公式推导
对于
\[ax+by=(a,b) \]不妨设 \(a>b\) ，
$(1) b=0 $ 则 \(x=1,y=0\).
$(2) a>b>0 $
设 \(ax_1+by_1=gcd(a,b)\)，\(bx_2+(a \mod b) y_2\)
由朴素欧几里得得：\(gcd(a,b)=gcd(b,a \mod b)\)
所以 \(ax_1 + by_1 = bx_2 + (a \mod b)y_2\)
即 \(ax_1 + by_1 = bx_2 + (a - \lfloor \frac{a}{b} \rfloor *b)y_2\)
化简得：\(ax_1 + by_1 = bx_2 + ay_2 - \lfloor \frac{a}{b} \rfloor *b *y_2\)
由贝祖等式得 \(x_1 = y_2 , y_1 = x_2 - \lfloor \frac{a}{b} \rfloor *y_2\)
裴蜀定理
若
\[a,b \in \mathbb Z \]则存在
\[x,y \in \mathbb Z,ax+by=(a,b) \]证明：由定理3易证。
- 推论：
整数 \(a\) 与 \(b\) 互质，
当且仅当存在整数 \(m,n\) 使得 \(ma+nb=1\).
证明：若 \(ma+nb=1\) ，由定理3得 \((a,b)=1\) ,易证。
二元一次不定方程
对于一些方程形如
\[ax+by=c \]如果 \(x = x_0, y = y_0\) 是方程的一个特解，
那么所有的解可以表示为：
\(x = x_0 + (b/d)n, y = y_0 - (a/d)n\) ，其中 \(n\) 是整数。
code：
//二元一次不定方程
#include<bits/stdc++.h>
#define int long long
using namespace std;
int G,a,b,c,d,x,y;
void exgcd(int a,int b,int& d,int& x,int& y) {
if(!b) {
d=a,x=1,y=0;
return ;
}
exgcd(b,a%b,d,x,y);
int t=x;
x=y,y=t-a/b*y;
return ;
}
signed main() {
scanf("%lld",&G);
while(G--) {
scanf("%lld%lld%lld",&a,&b,&c);
exgcd(a,b,d,x,y);
if(c%d!=0) {
printf("-1\n");
continue;
}
x*=c/d,y*=c/d;
int mx=b/d,my=a/d,minx=-1,maxx=-1,miny=-1,maxy=-1,t;
if(x>0) {
minx=x-(x/mx)*mx;
int ty=y+(x/mx)*my;
if(!minx) minx+=mx,ty-=my;
if(ty>0) maxx=minx+ty/my*mx-mx*(ty%my==0?1:0),t=ty/my+1-(ty%my==0?1:0);
}
else {
minx=x+(-x)/mx*mx+mx;
int ty=y-((-x)/mx+1)*my;
if(ty>0) maxx=minx+ty/my*mx-mx*(ty%my==0?1:0),t=ty/my+1-(ty%my==0?1:0);
}
if(y>0) {
miny=y-(y/my)*my;
int tx=x+(y/my)*mx;
if(!miny) miny+=my,tx-=mx;
if(tx>0) maxy=miny+tx/mx*my-my*(tx%mx==0?1:0);
}
else {
miny=y+(-y)/my*my+my;
int tx=x-((-y)/my+1)*mx;
if(tx>0) maxy=miny+tx/mx*my-my*(tx%mx==0?1:0);
}
if(maxx!=-1) printf("%lld %lld %lld %lld %lld\n",t,minx,miny,maxx,maxy);
else printf("%lld %lld\n",minx,miny);
}
return 0;
}
多元一次不定方程
对于方程形如
\[a_1x_1 + a_2x_2 + … + a_nx_n = c \]由前文所述，我们知道
\[a_1x_1 + a_2x_2 = k(a_1,a_2) \ (k \in \mathbb Z) \]所以原式就可以换成：
\[(a_1,a_2)x + a_3x_3 + … + a_nx_n = c \]重复以上操作，就可以得到：
\[(a_1,a_2,…,a_{n-1})x + a_nx_n =c \]再一层层解回去即可。
code:(仅供参考)
//多元一次不定方程
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5+5;
long long n,c,a[maxn],ans[maxn];
void exgcd(int a,int b,int& d,int& x,int& y) {
if(!b) {
d=a,x=1,y=0;
return ;
}
exgcd(b,a%b,d,x,y);
int temp=x;
x=y,y=temp-a/b*y;
return ;
}
void f(long long t,int now,int& nc) {
if(now<n) f(__gcd(t,a[now]),now+1,nc);
int x,y,d;
exgcd(t,a[now],d,x,y);
if(nc%d!=0) {
printf("-1");
exit(0);
}
x*=nc/d,y*=nc/d;
ans[now]=y;
if(now==2) ans[now-1]=x;
nc=t*x;
return ;
}
signed main() {
scanf("%lld%lld",&n,&c);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
f(a[1],2,c);
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
return 0;
}