前言

今天队友在群上问了一题，链接 (opens new window)，正解是拓展欧几里得，然而我的第一想法是同余最短路（因为我连拓展欧几里得都不会...）~

PS. 同余最短路的复杂度$O(nlogn),\ n=1e5$，拓展欧几里得复杂度$O(1)$

拓展欧几里得

求$ax+by=m$的一组解$(x,y)$

定理1: $ax+by=m$有整数解，则定有$gcd(a,b)\mid m$

下面用$g$来代替$gcd(a,b)$

可知$g\mid a$且$g\mid b$，因此，有$g \mid(ax+by)$

定理2: 若$gcd(a,b) \mid m$，则$ax+by=m$有整数解

事实上，这一定理可以用拓展欧几里得的过程来证明，但这里尝试用另一种方法证明。

---

设$ax+by$的最小正整数结果为$s$，现在证明$s=g$

由于$s$为$a,b$的线性组合，且$g\mid a, g\mid b$，因此$g\mid s$，即$g\le s$

$$\text{令} q=\lfloor \frac{a}{s} \rfloor, p=a\mod s$$

因而有

$$\begin{aligned}p & = a-qs\\ & = a-q(ax_0+by_0)\\ & = a(1-qx_0)-b(qy_0)\end{aligned}$$

因此$p$也是$a,b$的线性组合，又因为$s$为最小正整数，因此$p=0$，$s\mid a$

同理，可知$s$为$a,b$的公因数，又知$g$为$a,b$的最大公因数，因此$s\mid g$，即$s\le g$

综上，$s=g$

上述两条定理合在一起称为裴蜀定理

拓展欧几里得

这样一来，问题转化为求$ax+by=gcd(a,b)$的一组解$(x,y)$

代码只有四行

C++版

ll exgcd(ll a, ll b, ll & x, ll & y){
    if(b == 0) return x=1, y=0, a;
    ll g = exgcd(b, a%b, y, x);
    y -= a/b*x;
    return g;
}

Python版

def exgcd(a: int, b: int):
    if b == 0: return 1, 0, a
    y, x, g = exgcd(b, a % b)
    y -= a//b*x
    return x, y, g

下面来证明一下。

---

$ax_0+by_0=gcd(a,b)=gcd(b,a\%b)$

根据定理2，我们有$gcd(b, a\%b)=bx_1+(a\%b)y_1$

因而$ax_0+by_0=bx_1+(a\%b)y_1$

考虑展开求余符号'$\%$'，得到$ax_0+by_0=bx_1+(a -\lfloor \frac{a}{b} \rfloor b)y_1$

稍微化简得：$ax_0+by_0=ay_1+b(x_1-\lfloor \frac{a}{b} \rfloor y_1)$

显然$x_0,y_0$有一组解$x_0=y_1,y_0=x_1-\lfloor \frac{a}{b} \rfloor y_1$

---

设$a'=b,b'=a\%b$，显然有$max(a,b)\ge max(a', b')$，因而经过上述步骤之后，问题转化为了一个规模"更小"的子问题，可以递归求解。

考虑递归求解的边界，回想一下欧几里得算法的边界，定有$b=0$，即$ax_n+0y_n=g$，此时的$g=a$。因而$x_n=1,y_n=0$为一组可行解。我们把这组解回代，求出$(x_{n-1},y_{n-1}), (x_{n-2},y_{n-2})...$，最终求得$(x_0,y_0)$

现在得到$ax+by=gcd(a,b)$，要求$ax'+by'=m,\ gcd(a,b) \mid m$，显然有$x'=x\frac{m}{gcd(a,b)}$, $y'=y\frac{m}{gcd(a,b)}$

常用式子

已知$ax+by=gcd(a,b)$一组解$(x,y)$，其通解$(x',y')$为

$$f(x)=\left\{ \begin{aligned} x' = x+bt \\ y' = y+at \end{aligned} \right. (t \in Z)$$

求最小正整数解

假设我们对$ax+by=g$找到一组解$(x_n,y_n)$，那么对于$ax+by=c\ (gcd(a,b)\mid c)$，求$x$最小正整数解

令$g=gcd(a,b)$

有$x_n\frac{ac}{g}+y_n\frac{bc}{g}=g*\frac{c}{g}=c$，设$k=c/g$，因此$x_0=kx_n, y_0=ky_n$

考虑让新解$x_1=x_0-\delta_x$，为了使等式平衡，需要使$y_1=y_0+\delta_y$

即：$a\delta_x=b\delta_y$，因而$\frac{\delta_x}{\delta_y}=\frac{b}{a}=\frac{b/g}{a/g}\ (g=gcd(a,b))$

注意这里不应当约掉$g$，因为$\delta$越小，越能得到小的整数解

因而有$t=b/g,x_{min}=(x_0\%t+t)\%t$

# 洛谷P1516
def exgcd(a: int, b: int):
    if b == 0: return 1, 0, a
    y, x, g = exgcd(b, a%b)
    y -= a//b*x
    return x, y, g

x, y, m, n, L = map(int, input().split())
t, _, g = exgcd(n - m, L)
if (x - y) % g is not 0:
    print('Impossible')
else:
    t = t * ((x - y) // g)
    t = (t % (L // g) + (L // g)) % (L // g)
    print(t)

模板

Python:

def exgcd(a: int, b: int):
    if b == 0: return 1, 0, a
    y, x, g = exgcd(b, a % b)
    y -= a//b*x
    return x, y, g

def solve_linear(a, b, ans):
    """
    解ax+by=ans,且x为最小非负数
    """
    x, y, g = exgcd(a, b)
    factor = ans // g
    x, y = x * factor, y * factor
    m1, m2 = b // g, a // g
    delta = x // m1 # 向下取整, 而不是截尾
    x, y = x - delta * m1, y + delta * m2
    return x, y

C++:

自己把上面的代码翻译一下就好。。