P1516 青蛙的约会 题解

P1516 青蛙的约会 题解

\(\quad\)真是一道酣畅淋漓的数论题呐

1. 原题 P1516 青蛙的约会

题目描述

\(\quad\)两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

\(\quad\)我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经 \(0\) 度处为原点，由东往西为正方向，单位长度 \(1\) 米，这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 \(x\)，青蛙 B 的出发点坐标是 \(y\)。青蛙 A 一次能跳 \(m\) 米，青蛙 B 一次能跳 \(n\) 米，两只青蛙跳一次所花费的时间相同。纬度线总长 \(L\) 米。现在要你求出它们跳了几次以后才会碰面。

输入格式

输入只包括一行五个整数 \(x,y,m,n,L\)。

输出格式

输出碰面所需要的次数，如果永远不可能碰面则输出一行一个字符串 Impossible。

输入输出样例 #1

输入 #1

1 2 3 4 5

输出 #1

4

说明/提示

对于 \(100\%\) 的数据，\(1 \le x, y, m, n \le 2 \times 10^9\)，\(x \ne y\)，\(1 \le L \le 2.1 \times 10^9\)。

2. 简化题意

\(\quad\)在一个长度为 \(l\) 圆环上，青蛙A在 \(x\) 点，青蛙B在 \(y\) 点，青蛙A一步能走 \(m\) 米，青蛙B一步能走 \(n\) 米，问：两只青蛙何时能站在同一点上

3. 转化题意

\(\quad\)我们设跳 \(k\) 次后两只青蛙会相遇，根据题意，我们可以得到一个同余方程：

\[x + k \cdot m \equiv y + k \cdot n \pmod l \]

根据同余方程的性质，我们可以将这个柿子转化一下：

\[k \cdot m - k \cdot n \equiv y - x \pmod l \]

将左边提取公因式可以再次转化：

\[k \cdot (m - n) \equiv y - x \pmod l \]

这个柿子是什么意思呢？

不难发现，\(k \cdot (m - n)\) 与 \(y - x\) 的差是 \(l\) 的整数倍，那么我们可以再代入一个未知数 \(z \in \mathbb{Z}\) （\(z\)属于整数集）

那么我们将柿子进一步转化，转化为等式：

\[k \cdot (m - n) - (y - x) = z \cdot l \pod{z \in \mathbb{Z}} \]

我们将所有未知数转移到左边可以得到：

\[k \cdot (m - n) - z \cdot l = y - x \pod{z \in \mathbb{Z}} \implies k \cdot (m - n) + l \cdot (-z) = y - x \pod{z \in \mathbb{Z}} \]

仔细观察一下这个柿子，是不是有点眼熟？\(a \cdot x + b \cdot y = c\) 是不是恍然大悟？我去，这不就是一个 不定方程 吗！想到这里，你应该可以写了，只需要一个 拓展欧几里得 即可求解

4. 如何用 拓展欧几里得 ？

为了便于下面的理解，我们将用 \(a\) 代替 \(m - n\)，用 \(b\) 代替 \(l\)，用 \(c\) 代替 \(y - x\)，\(z\) 和 \(k\) 代表一个未知数

那么我们可以列出一个便于理解的柿子

\[a \cdot k - b \cdot z = c \implies a \cdot k + b \cdot (-z) = c \]

什么情况下无解呢？

我们知道exgcd是用来求解形如 \(a \cdot x + b \cdot y = gcd(a, b)\) 的不定方程，根据这个我们很容易得到 当且仅当 \(c\) 为 \(gcd(a, b)\) 的倍数时，\(a \cdot k + b \cdot (-z) = c\) 有解，所以就可以判断 if((b - a) % __gcd(n - m, l) != 0) 时，输出 Impossible

具体如何求解？

根据exgcd，我们求解了方程 \(a \cdot k + b \cdot (-z) = gcd(a, b)\) 得到了一组解 假设其为 \((k', z')\)，我们需要根据这个方程的这组解，求解出属于这道题的特解 \(k_特\)

观察这两个方程：

\[a \cdot k' + b \cdot (-z') = gcd(a, b) \]

\[a \cdot k_特 + b \cdot (-z_特) = c \]

我们考虑将第一个方程转化为第二个方程，只需要左右两边同时乘 \(\frac{c}{gcd(a, b)}\)：

\[a \cdot [k' \cdot (\frac{c}{gcd(a, b)})] + b \cdot [(-z') \cdot (\frac{c}{gcd(a, b)})] = gcd(a, b) \cdot \frac{c}{gcd(a, b)} = c \]

所以：

\[k_特 = k' \cdot (\frac{c}{gcd(a, b)}) \]

很好，恭喜你解决了这道题：

5. 参考代码

不建议直接看，建议自己把柿子推一遍，自己写

#include<bits/stdc++.h>
#define int long longusing namespace std;int exgcd(int a, int b, int &x, int &y){ // 精简版exgcd if(!b) return x = 1, y = 0, a;int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}signed main(){int a, b, n, m, l;cin>>a>>b>>n>>m>>l;int x, y;int d = exgcd(n - m, l, x, y);if((b - a) % d != 0) return 0 * puts("Impossible"); int t = abs(l / d);x *= (b - a) / d;cout<<(x % t + t) % t;return 0;
}