前置芝士(拓展欧几里得)
推导过程
设$x$次跳跃后两只青蛙相遇, 总共走了$y$圈.
根据题意可知A和B之间的距离为$b - a$米, 每次跳跃后之间的距离缩短$m - n$米.
可列出方程$(m - n)x = (b - a) + yL$.
移项可得$(m - n)x - yL = b - a$.
可以发现形式类似于拓展欧几里得$(m - n)x - yL = d$. $d = gcd(m - n, L)$
因此只需要$b - a$为$d$的倍数, 则有解, 否则无解.
因此问题可以转化为求$(m - n)x - yL = d$后将结果扩大$\frac{b - a}{d}$倍即可.
根据通项公式可以得到$x = x_0 + \frac{Lk}{d}$.
$y = y_0 + \frac{m - n}{d}$, 不过这里没啥用, 要注意的这里是加号, 有疑问的可以将$x = x_0 + \frac{Lk}{d}$带入推算一边.
设$tmp = abs(\frac{l}{d})$, 利用取模可以求得x的最小正整数解为$(x \% tmp + tmp) \% tmp$, 即最终答案.
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
LL a, b, m, n, l; cin >> a >> b >> m >> n >> l;
LL x, y;
LL d = exgcd(m - n, l, x, y);
if ((b - a) % d) cout << "Impossible" << endl;
else
{
x *= (b - a) / d;
LL tmp = abs(l / d);
cout << (x % tmp + tmp) % tmp << endl;
}
return 0;
}
请教下 “=(b−a)+yL ” 为什么右边一定是这个呢?