该题思路
怎么是困难题?挺简单的啊,梦回小学的追及问题
题意:两个青蛙在环形操场跑步, 假设$A$青蛙的速度是$m$, 此刻在$a$位置上, $B$ 青蛙的速度是$n$, 此刻在b
位置上。
则A
要追上B
,设时间$x$时刻追上, 此刻处在同一位置
则 $m * x + a - L*y = n * x + b$
$x, y是变量$
进行移项, 得
$(m - n)x - L * y = b - a$
可显然看出, 利用扩展欧几里得算法,即可求解
拓展:(对Exgcd算法的理解)
- 要想$ax + by = m$, 有解, 则 $m$ 一定是 $gcd(a, b)$的倍数, 否则无解
- $ax + by = gcd(a, b)$, 不止有一个解(x, y), 有多个解, 并且解有通项公式
拓展:解的通项公式的推导
$ \begin{equation} ax + by = gcd(a, b) \(1) \\\ ax_0 + by_0 = gcd(a, b) \(2) \end{equation} $
$(1) - (2)$得
$a(x - x_0) + b(y - y_0) = 0$
$\frac{a(x-x_0)}{gcd(a, b)}$ = $\frac{b(y_0-y)}{gcd(a, b)}$
$\because \frac{a}{gad(a,b)}$ 与 $\frac{b}{gad(a,b)}$ 互质, 且都为质数
$\therefore$ 要想两边等式成立的话, 则$(x-x_0)$必须包含 $\frac{b}{gad(a,b)}$这个质因子
$\therefore (x-x_0) = \frac{b}{gcd(a,b)} * t$
同理 $(y_0-y) = \frac{a}{gcd(a,b)} * t$
$\therefore$ 求出解的通项目公式
$$ \left\\{ \begin{aligned} & x = x_0 + \frac{b}{gcd(a, b) } * t \\\ & y = y_0 - \frac{a}{gcd(a, b)} * t \end{aligned} \right. $$
该题代码
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL& x, LL& y){
if(b == 0){
x = 1, y = 0;
return a;
}
LL x1, y1;
LL d = exgcd(b, a % b, x1, y1);
x = y1;
y = x1 - a / b * y1;
return d;
}
int main(){
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) puts("Impossible");
else{
x *= (b - a) / d;
LL t = abs(L / d);
cout << (x % t + t) % t << endl;
}
return 0;
}
请教下为什么一定只追 b−a + L*y 米啊?
可以不理解成追及问题,理解成在某一时刻两人最终在同一位置。 看第一个公式理解即可
那为什么一定是过了L * y倍数后在同一个位置呢?
不一定L整数倍也可能在同一位置吧?
就说为什么一定多 整数倍的L啊?
不可能是0.45L之类的么?
不解
或者像3.25L这样的
怎么可能会是小数呢,你两个人从不同的位置出发,最后到同一个地点,肯定是某个人比别人多跑整数圈啊。要么多跑1圈,2圈,3圈....,要么就多跑0圈。