思路:列出公式:设跳了a次后相遇,则
(x+am)%L=(y+bn)%L
(a(m-n))%L=(y-x)%L
就是解同余方程a*c≡d(L);
解线性同于方程:
ax≡b (mod n)的方程。此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除(记作 gcd(a,n) | b)。
在模 n 的完全剩余系 {0,1,…,n-1} 中,恰有 d 个解。
对于线性同余方程
ax ≡ b (mod n) (1)
若 d = gcd(a, n),d 整除 b ,那么b/d为整数。由裴蜀定理,存在整数对
(r,s) (可用辗转相除法求得)使得 ar+sn=d,因此 x0=rb/d是方程 (1) 的一个解。其他的解都关于n/d与 x 同余。即x≡x0+(n/d)*t......
阅读全文