给我自己的博客打个广告(没有写过几篇文章)

给定非负整数 $x, y, m, n, L$。

求最小的非负整数 $t$，使得 $x + tm \equiv y + tn \pmod L$

首先，将题目中同余式化为 $ax + by = c$ 的形式：

 1. 移项，得 $(x - y) + t(m - n) \equiv 0 \pmod L$，即 $L \mid (x - y) + t(m - n)$

 2. 设 $pL = (x - y) + t(m - n)$，整理，得 $pL + t(n - m) = (x - y)$

该方程有解当且仅当 $(L, n - m) \mid (x - y)$

就求出了方程 $pL + t(n - m) = (L, n - m)$ 的特解 $p_0, t_0$。

得到该方程的通解为 $p = \frac{x - y}{d}p_0 + k\frac{n - m}{d}, \quad t = \frac{x - y}{d}t_0 - k\frac{L}{d} \enspace (k \in \mathbb{Z}, \enspace d = (L, n - m))$

最后，对通解进行一些调整，就得到了最小整数解