P1516 青蛙的约会 推式子过程

· · 个人记录

懒得写题解，就把推算过程放上来

x+mt \equiv y+nt (\mod L)

因此

$(x+mt)-(y+nt) = aL (x+mt)-(y+nt)-aL = 0 (x-y)+t(m-n)-aL=0 t(n-m)+aL=(x-y)

设 w = n-m，b = x-y。

tw + aL=b 设 $c = GCD(w,L)

若 b \mod c \neq 0，无解。
对这个方程：tw+aL = c 求一组解 t0,a0
然后两边同时乘(b/c) 变为：

t0 \cdot w \cdot (b/c) + a0 \cdot L \cdot (b/c) = d

因为要求的是 t，那么本题的解就是：

t0 * (b/c)

然后因为要求最小解，那么处理一下：

ans = (t0 *(b/c) \mod (L \div c) + (L \div c)) \mod (L \div c)