天天看点

题解 P1516 【青蛙的约会】

有一个长度为 \(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。

注意无解情况。

代码