最近想刷一刷數論的題，就先找了道簡單的入手。
這一看就是exgcd求不定方程。
首先可以列出來：x + m * k ≡ y + n * k (mod L)
化簡：x + m * k - y - n * k = p * L
(m - n) * k - p * L = y - x
令a = m - n, b = L, c = y - x,于是
a * k - b * p = c
首先要保證a,b是正的。
代入exgcd求得ak + bp = 1的解k', p'，在gcd(a, b) | c的情況下，得出解k = k' * c / gcd(a, b)。
最小整數解就是(k + m) % m。
View Code