0题目原文（本地存了一份）
为什么要在这儿抄一份题面
原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。 所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。
转录自洛谷 P1516，日期见页头。两边不一致时信原站。
题目描述
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。 它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。 可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。 不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。 但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。 为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙 A 和青蛙 B，并且规定纬度线上东经 0 度处为原点，
由东往西为正方向，单位长度 1 米，这样我们就得到了一条首尾相接的数轴。
设青蛙 A 的出发点坐标是 x，青蛙 B 的出发点坐标是 y。
青蛙 A 一次能跳 m 米，青蛙 B 一次能跳 n 米，两只青蛙跳一次所花费的时间相同。
纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。
输入格式
输入只包括一行五个整数 x, y, m, n, L。
输出格式
输出碰面所需要的次数，如果永远不可能碰面则输出一行一个字符串 Impossible。
数据规模与约定
对于 100% 的数据，1 ≤ x, y, m, n ≤ 2 × 10⁹，x ≠ y，1 ≤ L ≤ 2.1 × 10⁹。
输入输出样例
输入
1 2 3 4 5
输出
4
⚠ 这一组样例把本页三个错法全放过了（都输出 4）。
★ 这道题挂在第 18 章的题单里，练的是「先判断该不该搜」
第 18 章讲的是迭代加深和双向 BFS，而这道题一点搜索都不用。 它放在这儿是为了练一个动作：动手之前先算一下，这题该不该搜。
而这一页会说明：这个判断是一道三十秒的算术题，不用写、不用测。
1第一反应：照着题面模拟
题面把过程写得清清楚楚：两只青蛙各跳各的，看什么时候落在同一点。照抄就是：
p1516Sim.cpp第一版：模拟
// P1516 的**第一版**：照题面模拟 —— 一次一次地跳，跳到重合为止。//// ⚠ 它**是对的**，而且写起来最快。可它跳几次才停？// 跳 t 次之后 `(m−n)·t ≡ (y−x) (mod L)`，t 的取值范围就是 `[0, L)` ——// 题面 `L ≤ 2.1 × 10⁹` ⇒ **最坏要跳 21 亿次**。//// ★★★ 这就是这一页要练的那件事：**「该不该搜」是一道三十秒的算术题** ——// 不用跑、不用测，把 t 的取值范围写出来就够了。// ⇒ 页面第 ② 步顺带量了一件更要紧的事：**随机数据会不会骗过你**。//// ⚠ 这一版还得有个「跳够 L 次就认输」的出口，否则无解时它永远不停// （两只青蛙的相对位置每步走 (m−n)，最多 L 步就循环回原处）。
#include <bits/stdc++.h>using namespace std;typedef long long ll;
int main(int argc, char** argv) { ll x, y, m, n, L; if (!(cin >> x >> y >> m >> n >> L)) return 0; ll a = ((x % L) + L) % L, b = ((y % L) + L) % L; for (ll t = 0; t < L; t++) { if (a == b) { cout << t << "\n"; if (argc > 1 && string(argv[1]) == "count") cerr << "steps=" << t << "\n"; return 0; } a = (a + m) % L; b = (b + n) % L; } cout << "Impossible\n"; if (argc > 1 && string(argv[1]) == "count") cerr << "steps=" << L << "\n"; return 0;}点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
它是对的（第 ④ 步用 22176 组小数据穷举验过）。问题只有一个：它要跳多少次？
2★★★ 「该不该搜」是一道三十秒的算术题
跳 t 次之后两只青蛙的位置分别是 x + m·t 和 y + n·t，在环上相遇就是
x + m·t ≡ y + n·t (mod L)
(m − n)·t ≡ (y − x) (mod L)★ 关键的一步
这是一个同余方程 A·t ≡ B (mod L)。而同余方程的解如果存在，
一定落在 [0, L) 里 —— 也就是说 t < L ≤ 2.1 × 10⁹。
⇒ 模拟版最坏要跳 21 亿次。不用跑就知道它不行。
⚠ 而这里有一个陷阱：顺手写的生成器会让模拟版看起来飞快。实测：
生成器里 L 的上限 |
100 | 10 000 | 10⁶ | 10⁸ |
|---|---|---|---|---|
| 模拟版平均跳几次 | 22 | 2 172 | 237 500 | 22 694 748 |
| 最多跳几次 | 95 | 9 704 | 916 441 | 93 972 707 |
L 取几十的时候，模拟版平均只跳 22 次 —— 你怎么测都测不出问题。
而它的耗时和 L 成正比，顶格就是 21 亿。
⇒ 这就是为什么要算而不是测：这道题的规模上限写在题面第一行， 而模拟版的步数上限等于它 —— 两行算术。
3正解：扩展欧几里得
A·t ≡ B (mod L)，其中 A = m − n、B = y − x：
g = gcd(A, L)，若B % g ≠ 0⇒ 无解（Impossible）；- 否则同除以
g，t = (B/g) · inv(A/g, L/g) mod (L/g)，取最小非负解。
p1516.cpp★ 这一版就能 AC
// P1516 青蛙的约会 —— 扩展欧几里得（★ 这一版就能 AC）//// ★★★ 这道题挂在第 18 章的题单里，是为了练一件**和搜索无关**的事：// **先判断该不该搜。** 而这个判断是一道**三十秒的算术题**，不用试、不用测。//// 题面：两只青蛙在长 L 的环上，起点 x、y，每次分别跳 m、n 米，问几次之后同时落在同一点。// 跳 t 次之后：`x + m·t ≡ y + n·t (mod L)`// 移项： `(m − n)·t ≡ (y − x) (mod L)`// ⇒ 这就是一个**同余方程** `A·t ≡ B (mod L)`，扩展欧几里得直接解。//// ★ 而「该不该搜」的算术是这样的：t 的取值范围就是 `[0, L)`，而题面 `L ≤ 2.1 × 10⁹` ——// 一步一步跳最坏要跳 21 亿次。⇒ **不用跑就知道模拟不行**（页面第 ② 步量了它）。//// 解法（`A·t ≡ B (mod L)`）：// g = gcd(A, L)；`B % g != 0` ⇒ 无解（Impossible）；// 否则同除以 g，`t = (B/g) · inv(A/g, L/g) mod (L/g)`，取最小非负解。//// ⚠ 两个必须做对的地方（页面第 ③ ④ 步各量了一个）：// ① **开 long long**：`x, y, m, n ≤ 2 × 10⁹` 本身就装不进 int；// 而 `(B/g) · inv` 最大约 `2.1×10⁹ × 2.1×10⁹ ≈ 4.4 × 10¹⁸`，long long（9.2 × 10¹⁸）刚好够。// ② **负数取模要调正**：`A = m − n` 和 `B = y − x` 都可能是负的，// 而 C++ 的 `%` 对负数是**向零取整**（`-7 % 5 == -2`，不是 3）。
#include <bits/stdc++.h>using namespace std;typedef long long ll;
/** 扩展欧几里得：返回 gcd(a,b)，并求出 a·p + b·q = gcd */static ll exgcd(ll a, ll b, ll& p, ll& q) { if (!b) { p = 1; q = 0; return a; } ll g = exgcd(b, a % b, q, p); q -= a / b * p; return g;}
int main() { ll x, y, m, n, L; if (!(cin >> x >> y >> m >> n >> L)) return 0;
ll A = ((m - n) % L + L) % L; // ★ 调正，见文件头 ② ll B = ((y - x) % L + L) % L;
ll p, q; ll g = exgcd(A, L, p, q); if (B % g) { cout << "Impossible\n"; return 0; }
ll mod = L / g; ll inv = ((p % mod) + mod) % mod; // A/g 在模 L/g 下的逆元 ll t = (B / g) % mod * inv % mod; // ★ 最大约 4.4e18，long long（9.2e18）刚好够 cout << t << "\n"; return 0;}点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★ 它对不对，不用信我 —— 拿模拟版逐组比
小数据上把 x, y ≤ 8、m, n ≤ 6、L ≤ 12 全部枚举一遍，22 176 组：
exgcd 正解和模拟版不一致 0 次。
⇒ 这就是模拟版真正的用处：它跑不动大数据，但它是最可靠的参照物。
4★★★ 而这道题的对拍，有一个结构性的两难
这道题最出名的坑是要开 long long（题面第一行 x, y, m, n ≤ 2 × 10⁹ 就装不进 int）：
p1516Int.cpp错法一：用 int
// P1516 的**错法一**：算法一模一样，只把 `long long` 换成了 `int`。//// 题面第一行就写着 `1 ≤ x, y, m, n ≤ 2 × 10⁹`，而 int 的上限是 2147483647 ——// **光是读进来就装不下**。//// ★ 这一版存在的意义是量一件事：**照题面随机造数据，多久才碰到一次溢出**。// 页面第 ③ 步把这条曲线画出来了 —— 而顺手写的小数据生成器**一次都抓不到**。
#include <bits/stdc++.h>using namespace std;typedef int ll; // ★ 错在这里
/** 扩展欧几里得：返回 gcd(a,b)，并求出 a·p + b·q = gcd */static ll exgcd(ll a, ll b, ll& p, ll& q) { if (!b) { p = 1; q = 0; return a; } ll g = exgcd(b, a % b, q, p); q -= a / b * p; return g;}
int main() { ll x, y, m, n, L; if (!(cin >> x >> y >> m >> n >> L)) return 0;
ll A = ((m - n) % L + L) % L; // ★ 调正，见文件头 ② ll B = ((y - x) % L + L) % L;
ll p, q; ll g = exgcd(A, L, p, q); if (B % g) { cout << "Impossible\n"; return 0; }
ll mod = L / g; ll inv = ((p % mod) + mod) % mod; // A/g 在模 L/g 下的逆元 ll t = (B / g) % mod * inv % mod; // ★ 最大约 4.4e18，long long（9.2e18）刚好够 cout << t << "\n"; return 0;}点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
它什么时候现形？算得出来：算式里最大的那一步是 (B/g) · inv，两个因子都小于 L，
所以只要 L² ≥ 2³¹ 就可能溢出 ——
46340² = 2 147 395 600 < 2³¹ = 2 147 483 648 ≤ 46341² = 2 147 488 281实测（每档 300 组）正好落在这条线上：
L 的上限 |
20 | 1 000 | 46 340 | 46 341 | 100 000 | 10⁷ | 2 × 10⁹ |
|---|---|---|---|---|---|---|---|
int 版错的组数 |
0 | 0 | 0 | 0 | 31 | 218 | 207 |
★★★ 两难：参照物只在 L 小时能用，而溢出只在 L 大时发生
把两条线画在一起：
L = 10 1000 46341 10^8 2.1e9
+----------+----------+------------+-----------+
模拟版跑得动 |<-------------------------->|
(跳 ~L/2 次；L = 10^8 时约 2270 万次)
int 版开始出错 |<-------------------------->|
两者的重叠区 |<---------->|
46341 .. 10^8
而顺手写的生成器待在这儿
^
L 取几十 —— 离重叠区差六个数量级- 模拟版（唯一可靠的参照物）要跳
~L/2次 ⇒L一大就跑不完； int溢出只在L > 46341之后才发生。
⇒ 顺手写的生成器（L 取几十）结构上一次都抓不到溢出（前四档全是精确的 0），
而把 L 直接调到顶格，模拟版又当不了参照物了。
★ 好消息是这两条线留了一段重叠区：L ∈ [46341, 10⁸]，跨三个数量级 ——
在那一段里两件事能同时做。⚠ 而顺手写的生成器离它差六个数量级。
★★ 这是第 11 章 P1908 那条的又一次现场 （「对拍查不出溢出」的真正死结是参照物是暴力）， 只是这道题干净到可以把两条线都算出来、把重叠区指出来。
5⚠ 第二个坑：C++ 的 `%` 对负数是向零取整
A = m − n 和 B = y − x 都可能是负的，而 -7 % 5 == -2，不是 3。
p1516Neg.cpp错法二：忘了调正负数
// P1516 的**错法二**：忘了把 `A = m − n` 和 `B = y − x` 调成非负。//// C++ 的 `%` 对负数是**向零取整**：`-7 % 5 == -2`，不是 3。// ⇒ `m < n`（青蛙 A 跳得慢）或者 `y < x` 的时候，A 或 B 就是负的，后面全乱。//// ★ 而这个错法有意思在**它一半的输入是对的**：只要 `m > n` 且 `y > x` 就没事。// ⇒ 页面第 ④ 步量了它的抓获率 —— 而**官方样例正好落在「对」的那一半**。
#include <bits/stdc++.h>using namespace std;typedef long long ll;
/** 扩展欧几里得：返回 gcd(a,b)，并求出 a·p + b·q = gcd */static ll exgcd(ll a, ll b, ll& p, ll& q) { if (!b) { p = 1; q = 0; return a; } ll g = exgcd(b, a % b, q, p); q -= a / b * p; return g;}
int main() { ll x, y, m, n, L; if (!(cin >> x >> y >> m >> n >> L)) return 0;
ll A = (m - n) % L; // ★ 错在这里：没有调正 ll B = (y - x) % L;
ll p, q; ll g = exgcd(A, L, p, q); if (B % g) { cout << "Impossible\n"; return 0; }
ll mod = L / g; ll inv = ((p % mod) + mod) % mod; // A/g 在模 L/g 下的逆元 ll t = (B / g) % mod * inv % mod; // ★ 最大约 4.4e18，long long（9.2e18）刚好够 cout << t << "\n"; return 0;}点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
L 的上限 |
20 | 1 000 | 10⁶ |
|---|---|---|---|
| 错的组数（300 组） | 110 | 95 | 116 |
| 其中直接打出负数的 | 92 | 94 | 116 |
★ 它三分之一的输入是错的，而且错得很显眼 —— 可官方样例正好躲开了
只要 m > n 且 y > x 它就没事；样例 1 2 3 4 5 里 m < n，
按说该踩上……可 (3−4) % 5 == -1，后面的 exgcd 一路负下去，
最后又绕回了正确答案 4。
⇒ 一个「三分之一输入会错、而且多半直接打出负数」的 bug，官方样例照样放过。 ★ 这一天做的四道题里，官方样例的表现是： P2324 挡住了、P1032 两个都没挡住、这道题三个都没挡住。 「样例挡不挡得住」真的只能一个一个试。
6度量程序和生成器
p1516Count.cpp度量程序
// P1516 的度量程序 —— 这一页所有数字都出自这一份。//// `./p1516Count` 人看的版本// `./p1516Count csv` 一行一项，给 scripts/check-viz.mjs 写断言用//// 五段：// ① 官方样例：四个版本各输出什么（★ 三个错法它都放过了）；// ② ★ 正解 ≡ 模拟版：小数据上逐组比，确认 exgcd 那一版真的对；// ③ ★★★ **「该不该搜」是一道算术题**：答案 t 的取值范围就是 `[0, L)`，// 而模拟版要跳 t 次 —— 量一量随机数据上 t 有多大；// ④ ★★★ `int` 版的抓获率曲线，以及它的**精确分界 46340**// （`46340² < 2³¹ ≤ 46341²`）；// ⑤ ★ 忘了调正负数那一版的抓获率 —— 它**一半的输入是对的**。
#include <bits/stdc++.h>using namespace std;typedef long long ll;
static bool CSV = false;static void row(const char* key, const vector<long long>& v) { if (!CSV) return; printf("%s", key); for (long long x : v) printf(",%lld", x); printf("\n");}
static ll exgcd(ll a, ll b, ll& p, ll& q) { if (!b) { p = 1; q = 0; return a; } ll g = exgcd(b, a % b, q, p); q -= a / b * p; return g;}
/** 正解。返回 -1 表示 Impossible。 */static ll solve(ll x, ll y, ll m, ll n, ll L) { ll A = ((m - n) % L + L) % L, B = ((y - x) % L + L) % L; ll p, q, g = exgcd(A, L, p, q); if (B % g) return -1; ll mod = L / g; ll inv = ((p % mod) + mod) % mod; return (B / g) % mod * inv % mod;}
/** 忘了调正负数的那一版（原样保留它的算术，包括算出负数） */static ll solveNeg(ll x, ll y, ll m, ll n, ll L) { ll A = (m - n) % L, B = (y - x) % L; ll p, q, g = exgcd(A, L, p, q); if (g == 0 || B % g) return -1; ll mod = L / g; if (mod == 0) return -1; ll inv = ((p % mod) + mod) % mod; return (B / g) % mod * inv % mod;}
/** 用 int 重算一遍（错法一）：所有中间量都截断成 32 位 */static int exgcdI(int a, int b, int& p, int& q) { if (!b) { p = 1; q = 0; return a; } int g = exgcdI(b, a % b, q, p); q -= a / b * p; return g;}static ll solveInt(ll x0, ll y0, ll m0, ll n0, ll L0) { int x = (int)x0, y = (int)y0, m = (int)m0, n = (int)n0, L = (int)L0; if (L == 0) return -1; int A = ((m - n) % L + L) % L, B = ((y - x) % L + L) % L; int p, q, g = exgcdI(A, L, p, q); if (g == 0 || B % g) return -1; int mod = L / g; if (mod == 0) return -1; int inv = ((p % mod) + mod) % mod; return (ll)(int)((B / g) % mod * inv % mod);}
/** 模拟版：一步一步跳，最多跳 L 次。返回步数或 -1。 */static ll simulate(ll x, ll y, ll m, ll n, ll L, ll cap, bool& blew) { blew = false; ll a = ((x % L) + L) % L, b = ((y % L) + L) % L; for (ll t = 0; t < L; t++) { if (t >= cap) { blew = true; return -2; } if (a == b) return t; a = (a + m) % L; b = (b + n) % L; } return -1;}
/** 和 p1516Gen.cpp 逐字一致 */static void gen(int seed, ll hi, ll& x, ll& y, ll& m, ll& n, ll& L) { mt19937_64 rng((unsigned)seed * 2654435761ull + 37ull); hi = max(2LL, min(2000000000LL, hi)); L = (ll)(rng() % (hi - 1)) + 2; x = (ll)(rng() % hi) + 1; do { y = (ll)(rng() % hi) + 1; } while (y == x); m = (ll)(rng() % hi) + 1; n = (ll)(rng() % hi) + 1;}
int main(int argc, char** argv) { CSV = (argc > 1 && string(argv[1]) == "csv");
/* ① 官方样例 */ { bool blew; ll a = solve(1, 2, 3, 4, 5), b = simulate(1, 2, 3, 4, 5, 1000, blew); ll c = solveInt(1, 2, 3, 4, 5), d = solveNeg(1, 2, 3, 4, 5); if (!CSV) printf("① 官方样例 1 2 3 4 5：正解 %lld｜模拟 %lld｜int 版 %lld｜忘调正负数 %lld" "（★ 三个都是 4，样例全放过了）\n", a, b, c, d); row("sample", {a, b, c, d}); }
/* ② 正解 ≡ 模拟版（小数据穷举） */ { int cases = 0, diff = 0; for (ll x = 1; x <= 8; x++) for (ll y = 1; y <= 8; y++) { if (x == y) continue; for (ll m = 1; m <= 6; m++) for (ll n = 1; n <= 6; n++) for (ll L = 2; L <= 12; L++) { bool blew; cases++; if (solve(x, y, m, n, L) != simulate(x, y, m, n, L, 100000, blew)) diff++; } } if (!CSV) printf("\n② 小数据穷举 %d 组：exgcd 正解和模拟版不一致 %d 次\n", cases, diff); row("same", {cases, diff}); }
/* ③ ★★★ 「该不该搜」：t 有多大 */ { if (!CSV) printf("\n③ 模拟版要跳多少次（每档 300 组，只统计有解的）\n"); vector<long long> out; for (ll hi : {100LL, 10000LL, 1000000LL, 100000000LL}) { ll sum = 0, mx = 0; int cnt = 0; for (int s = 1; s <= 300; s++) { ll x, y, m, n, L; gen(s, hi, x, y, m, n, L); ll t = solve(x, y, m, n, L); if (t < 0) continue; sum += t; mx = max(mx, t); cnt++; } out.push_back(cnt ? sum / cnt : 0); out.push_back(mx); if (!CSV) printf(" L 上限 %11lld：有解 %3d / 300，平均跳 %10lld 次，最多 %11lld 次\n", hi, cnt, cnt ? sum / cnt : 0, mx); } row("steps", out); }
/* ④ ★★★ int 版的抓获率曲线 ＋ 精确分界 */ { if (!CSV) printf("\n④ int 版从哪一档开始错（每档 300 组）\n"); vector<long long> out; for (ll hi : {20LL, 1000LL, 46340LL, 46341LL, 100000LL, 10000000LL, 2000000000LL}) { int bad = 0; for (int s = 1; s <= 300; s++) { ll x, y, m, n, L; gen(s, hi, x, y, m, n, L); if (solveInt(x, y, m, n, L) != solve(x, y, m, n, L)) bad++; } out.push_back(bad); if (!CSV) printf(" L 上限 %11lld：错 %3d / 300\n", hi, bad); } row("intCatch", out); // 精确分界：46340² < 2³¹ ≤ 46341² long long a = 46340LL * 46340, b = 46341LL * 46341; if (!CSV) printf(" ★ 分界线是算出来的：46340² = %lld < 2³¹ = 2147483648 ≤ 46341² = %lld\n", a, b); row("bound", {a, 2147483648LL, b}); }
/* ⑤ 忘了调正负数：它一半的输入是对的 */ { if (!CSV) printf("\n⑤ 忘了调正负数那一版（每档 300 组）\n"); vector<long long> out; for (ll hi : {20LL, 1000LL, 1000000LL}) { int bad = 0, negOut = 0; for (int s = 1; s <= 300; s++) { ll x, y, m, n, L; gen(s, hi, x, y, m, n, L); ll r = solveNeg(x, y, m, n, L); if (r != solve(x, y, m, n, L)) bad++; if (r < -1) negOut++; } out.push_back(bad); out.push_back(negOut); if (!CSV) printf(" L 上限 %8lld：错 %3d / 300（其中直接打出负数的 %d 组）\n", hi, bad, negOut); } row("negCatch", out); } return 0;}点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
p1516Gen.cpp数据生成器
// P1516 对拍生成器：`./p1516Gen <seed> [L 的上限]`// L 的上限 默认 20 —— ★★★ **这个旋钮是这一页的全部**//// 造法：随机 `L ∈ [2, 上限]`，随机 `x ≠ y ∈ [1, 上限]`，随机 `m, n ∈ [1, 上限]`。// （题面：`1 ≤ x, y, m, n ≤ 2×10⁹`、`x ≠ y`、`1 ≤ L ≤ 2.1×10⁹`。）//// ★★★ 为什么「L 的上限」是这一页的全部：这道题的对拍有一个**结构性的两难** ——// · 参照物只能是**模拟版**（一步一步跳），而它要跳最多 `L` 次 ⇒ **L 一大就跑不完**；// · 而 `int` 溢出**只在 L 大的时候才发生**（页面第 ③ 步算得出精确分界）。// ⇒ 顺手写的生成器（L 取几十）**结构上一次都抓不到溢出**，// 而把 L 调到能抓溢出的那一档，模拟版又当不了参照物了。// ★ 好在这两条线之间**留了一段重叠区**，页面第 ③ 步把它量了出来。
#include <bits/stdc++.h>using namespace std;typedef long long ll;
int main(int argc, char** argv) { unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1; ll hi = argc > 2 ? atoll(argv[2]) : 20; mt19937_64 rng(seed * 2654435761ull + 37ull); hi = max(2LL, min(2000000000LL, hi));
ll L = (ll)(rng() % (hi - 1)) + 2; ll x = (ll)(rng() % hi) + 1, y; do { y = (ll)(rng() % hi) + 1; } while (y == x); ll m = (ll)(rng() % hi) + 1, n = (ll)(rng() % hi) + 1; printf("%lld %lld %lld %lld %lld\n", x, y, m, n, L); return 0;}点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
7一页纸
| 关键的一步 | 把题面翻成同余方程 (m−n)·t ≡ (y−x) (mod L)，扩展欧几里得解它 |
| 哪一版能 AC | p1516.cpp；模拟版最坏要跳 21 亿次 |
| 该不该搜 | 一道三十秒的算术题：同余方程的解一定在 [0, L) 里，而 L ≤ 2.1 × 10⁹ |
| 最容易挂的一行 | int —— 题面第一行 2 × 10⁹ 就装不下；分界线算得出来：L > 46341 |
| 第二容易挂的一行 | 负数取模要调正（-7 % 5 == -2）—— 三分之一的输入会错，多半直接打出负数 |
| 这一页的主线 | 对拍的结构性两难：参照物（模拟版）只在 L 小时能跑，而 int 溢出只在 L > 46341 时发生 —— 重叠区是 [46341, 10⁸]，而顺手写的生成器（ L 取几十）离它差六个数量级 |
| 样例的表现 | ⚠ 三个错法全放过了 |