有一个长度为 \(l\) 的圆环,圆环上有两个点 \(A,B\) ,分别位于 \(x,y\) ,每次分别可跳 \(m,n\) 个单位,问跳多少次相遇。无解输出 <code>Impossible</code> 。
对此可列出同余方程:
\[(x+am)\equiv (y+an)(\bmod l)
\]
展开:
\[(x+am)-(y+an)=bl
\[x-y+a(m-n)=bl
\[a(m-n)-bl=y-x
这里 \(a,b\) 即为我们所求。扩欧后推广解就行了。但由于 \(x=x_0+ k\frac{b}{\gcd(a,b)}\) ,所以求最小正整数要对 \(\frac{b}{\gcd(a,b)}\) 取模。
开LL。
注意无解情况。
代码