ToB企服应用市场:ToB评测及商务社交产业平台

标题: 二元一次不定方程（Exgcd）（更方便的解法） [打印本页]

作者: 雁过留声 时间: 2024-7-22 14:30
标题: 二元一次不定方程（Exgcd）（更方便的解法）
扩展欧几里得算法（Exgcd）

裴蜀定理

对于任意一组整数 $a,b$，存在一组整数 $x,y$，满足 $ax+by=\gcd(a,b)$。
Proof：

考虑数学归纳法。
当 $b=0$ 时，由于 $\gcd(a,0)=a$，则对于 $ax+0y=a$ 这个不定方程，$x=1$，$y$ 取任意整数。
假设存在一组整数 $x,y$，满足 $bx+(a\bmod b)y=\gcd(b,a\bmod b)=\gcd(a,b) $。
那么接下来证明也存在一组整数 $x',y'$ 满足 $ax'+by'=\gcd(a,b)$。

\[\begin{aligned}bx+(a\bmod b)y &= bx+(a-b\lfloor\dfrac{a}{b}\rfloor)y\\&= bx+ay-b\lfloor\dfrac{a}{b}\rfloor y\\&= ay+b(x-\lfloor\dfrac{a}{b}\rfloor y)\end{aligned}\]
当 $x'=y,y'=x-\lfloor\dfrac{a}{b}\rfloor y$ 时满足条件。
那么利用辗转相除法举行递归，总能递归到 $b=0$ 的环境。命题得证。
Exgcd

求关于 $x,y$ 的方程 $ax+by=c$ 的整数解。
设 $d=\gcd(a,b)$，方程有整数解的充要条件是 $d\mid c$。

Proof：
设 $a=k_1d,b=k_2d$，则有 $k_1dx+k_2dy=c \Rightarrow k_1x+k_2y=\dfrac{c}{d}$。
先证须要性：由于 $\dfrac{c}{d}$ 必须为整数，则 $d \mid c$。
再证充实性：上式中，$k_1\perp k_2$，则方程 $k_1x'+k_2y'=1$ 肯定有整数解。由于 $\dfrac{c}{d} \in\mathbb{Z}$，那么原方程也肯定有整数解。

先将方程化简，两边同除以 $d$。此时 $a,b$ 互质。
为了方便表述，下面提到的方程都是化简后的方程。
那么我们可以先利用裴蜀定理求出 $ax'+by'=1$ 的一组特解 $x',y'$，从而求出原方程的一组特解 $x_0=cx’,y_0=cy'$。
考虑怎样求出通解。
让 $x$ 加上一个数，那么 $y$ 就要减去一个数。设这两个数为 $\Delta_x,\Delta_y$，则有：

\[\begin{aligned}a(x+\Delta_x)+b(y-\Delta_y) &= c\\ax+a\Delta_x+by-b\Delta_y &= c\\a\Delta_x-b\Delta_y&=0\\a\Delta_x &= b\Delta_y \\\dfrac{a}{b} &= \dfrac{\Delta_y}{\Delta_x}\end{aligned}\]
由于 $a,b$ 互质，则 $\dfrac{a}{b}$ 为最简整数比，则有 $a \mid \Delta_y$ 且 $\ b\mid \Delta_x$。
由于 $\Delta_x,\Delta_y \in \mathbb{Z}$，则 $\Delta_x$ 最小取到 $b$，$\Delta_y$ 最小取到 $a$。
通解即为：

\[\begin{cases}x=x_0+kb\\y=y_0+ka\\\end{cases}(k\in \mathbb{Z})\]
代回原方程，可以消掉 $kb,ka$。
接下来考虑，当存在正整数解时，怎样求出最小正整数解与正整数解的个数。
对 $x$ 的通解举行变形，求 $x$ 的最小正整数解 $x_1$：

\[\begin{aligned}x_1 \bmod b &= (x_0+kb) \bmod b\\x_1 \bmod b &= x_0 \bmod b\\x_1&=(((x_0-1) \bmod b)+b)\bmod b+1\end{aligned}\]
先减一是为了制止 $x_0 \bmod a $ 一开始就为 $0$ 的环境，从而保证 $x_1>0$。
易得，当 $x$ 增大时，$y$ 减小。当 $x$ 取 $x_1$ 时，$y$ 取到最大正整数解 $y_2$。
同理，求出 $y$ 的最小正整数解 $y_1$，当 $y$ 取 $y_1$ 时，$x$ 取到最大正整数解 $x_2$。
由通解公式可得，$x$ 每两个整数解之间相差 $b$，$y$ 每两个整数解之间相差 $a$。
正整数解的个数即为 $\dfrac{x_2-x_1}{b}+1$ 或 $\dfrac{y_2-y_1}{a}+1$。
Ex.1 【模板】二元一次不定方程 (exgcd)

根据上面的分析，套用公式即可。
[code]ll T,A,B,C,x,y,d,x1,x2,y1,y2,cnt; ll GetX(ll Y){return (C-B*Y)/A;}ll GetY(ll X){return (C-A*X)/B;}ll Exgcd(ll a,ll b,ll &x,ll &y){ if(b==0) return x=1,y=0,a; ll res=Exgcd(b,a%b,x,y); ll z=x; x=y; y=z-(a/b)*y; return res;}void Solve(){ read(A),read(B),read(C); d=Exgcd(A,B,x,y); if(C%d) return puts("-1"),void(); A/=d,B/=d,C/=d; x*=C,y*=C; x1=((x-1)%B+B)%B+1; y2=GetY(x1); y1=((y-1)%A+A)%A+1; x2=GetX(y1); cnt=(x2-x1)/B+1; if(y2

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)