The 2025 ICPC 德国 German Collegiate Programming Contest——A. Around the Table · znzryb
## 题目大意
**题目名称**：Around the Table
**题意总结**：
公园里有一张乒乓球桌，初始时左边队列有 $\ell$ 个人，右边队列有 $r$ 个人。左边队首的人先持球。
游戏规则如下：
1. 持球者将球打到对面，然后立刻跑到**对面**队列的队尾。
1. 对面队首的人接球后成为新的持球者，重复上述过程。
假设游戏进行无限次（$10^{10^{100}}$ 次击球），你需要计算总共会出现多少对不同的“对决组合”。
**注意**：两个人面对面即为一次对决，A 对战 B 与 B 对战 A 被视为同一种组合，不重复计算。
**输入格式**：
一行包含两个整数 $\ell$ 和 $r$ （$2 \le \ell \le 10^9, 1 \le r \le 10^9$），分别表示初始时左侧和右侧的人数。
**输出格式**：
输出一个整数，表示会出现的不同对决组合的数量。
**样例 1 解释**：
输入：`2 2`
输出：`6`
假设左边初始为 A, B，右边初始为 D, E。
流程推演：
注意啊，题目实际上求的是**面对面情况**，就是**面对面过的这个 pair 的数量**。当然，这 **Pair 是一个无序对**。
1. **A 对 D**（记录组合 {A, D}）。A 击球后去右边队尾。局面变更为：左 [B]，右 [D, E, A]。
1. **B 对 D**（记录组合 {B, D}）。D 击球后去左边队尾。局面变更为：左 [B, D]，右 [E, A]。
1. **B 对 E**（记录组合 {B, E}）。B 击球后去右边队尾。局面变更为：左 [D]，右 [E, A, B]。
1. **D 对 E**（记录组合 {D, E}）。E 击球后去左边队尾。局面变更为：左 [D, E]，右 [A, B]。
1. **D 对 A**（组合 {A, D} 已存在）。D 击球后去右边队尾。局面变更为：左 [E]，右 [A, B, D]。
1. **E 对 A**（记录组合 {E, A}）。A 击球后去左边队尾。局面变更为：左 [E, A]，右 [B, D]。
1. **E 对 B**（组合 {B, E} 已存在）。E 击球后去右边队尾。局面变更为：左 [A]，右 [B, D, E]。
1. **A 对 B**（记录组合 {A, B}）。B 击球后去左边队尾。局面变更为：左 [A, B]，右 [D, E]。
此时回到初始局面（A 对 D），循环结束。
总共出现的不重复组合为：{A, D}, {B, D}, {B, E}, {D, E}, {E, A}, {A, B}，共 6 种。
## 思路讲解
::: AI 提示 1（遇到这种问题还是要打表，还是要打表。）
好的，你还没有开始写。这道题其实有很漂亮的结构，我来给你一些分层提示，你可以看一个想一下，不够再往下看。
---
**提示 1（方向性）**：手动模拟一下小例子（比如 ℓ=2, r=2），把所有玩家编号 0 到 n-1，观察每次击球后队列的变化。特别注意：**每两次击球**（左打一次、右打一次）之后，两边队列的长度会恢复到 ℓ 和 r。那么这两次击球之后，队首面对的人**相比之前偏移了多少**？
---
**提示 2（核心观察）**：给 n = ℓ + r 个人编号，排成一个**环**。初始时左队首是 0 号，右队首是 ℓ 号。你会发现：
- 第 2k 次击球时，面对的一对人是 $\{k \bmod n,\; (k + \ell) \bmod n\}$
- 第 2k+1 次击球时，面对的一对人是 $\{(k+1) \bmod n,\; (k + \ell) \bmod n\}$
也就是说，偶数次击球产生的配对，环上距离固定为 $\ell$（等价于 $r$）；奇数次击球产生的配对，环上距离固定为 $\ell - 1$（等价于 $r + 1$）。
---
**提示 3（计数）**：问题变成了：在 $\mathbb{Z}_n$ 的环上，
- 距离为 $d_1 = \min(\ell, r)$ 的无序对有多少个？
- 距离为 $d_2 = \min(\ell - 1, r + 1)$ 的无序对有多少个？
- 这两个集合是否可能重合？
对于一个固定距离 $d$（$1 \le d \le n/2$），$n$ 个人的环上距离恰好为 $d$ 的无序对有多少个？想想什么时候是 $n$，什么时候是 $n/2$。
然后考虑 $d_1$ 和 $d_2$ 什么时候相等（此时两类配对产生的是同一个集合，不能重复计数）。
---
这三层提示应该足够你推出最终公式了。要继续深入还是先自己想一下？
:::
```cpp
_______________[ Sample Testcase #1 INPUT ]_______________
2 2
_______________[ Sample Testcase #1 OUTPUT]_______________
6
[-] FAILURE: RUNTIME ERROR
2 3
1 3
1 4
3 4
3 2
4 2
4 1
2 1
2 3
1 3
1 4
```
我们还是把第一个数字给反转一下吧，把第一个数字反转一下更加符更加符合我们人类的这个直觉。
你会发现一二三四五，这样子是轮流出现的，是轮流出现的，就像模运算一样。
```cpp
_______________[ Sample Testcase #1 INPUT ]_______________
2 2
_______________[ Sample Testcase #1 OUTPUT]_______________
6
[-] FAILURE: RUNTIME ERROR
1 3
2 3
2 4
3 4
3 1
4 1
4 2
1 2
1 3
2 3
2 4
_______________[ Sample Testcase #2 INPUT ]_______________
2 3
_______________[ Sample Testcase #2 OUTPUT]_______________
10
[-] FAILURE: RUNTIME ERROR
1 3
2 3
2 4
3 4
3 5
4 5
4 1
5 1
5 2
1 2
1 3
2 3
2 4
3 4
3 5
4 5
4 1
5 1
5 2
1 2
1 3
```
规律大概是这样的，不过还是不是特别清楚呢。我们使用零 base 的下标再注释一下。
这下子这个规律就非常清楚了。不过注意啊，其实就是**第奇数个加 gap ，第偶数个加 gap-1**，它不会加 gap 加二什么之类的。
那么奇数位，$(i,(i+gap)\mod n)$，这个东西内部，有没有可能重复呢？不难写出：
$$
i\equiv i'+gap \\
i+gap\equiv i' \\
$$
```ascii art
i ≡ i' + gap (mod n) ①
i + gap ≡ i' (mod n) ②
① - ②: -gap ≡ gap (mod n)
即: 2 * gap ≡ 0 (mod n)
```
注意啊，处理这种同余式子**可以加减乘**，**但是不能除**。如果除的话，必须确保逆元存在。逆元存在条件就是你要除的数字和和这个 mod n 的这个 n 是互质的。
注意啊，处理各种各样的式子，这个都是**先要把这个变量给消掉**，对吧？**这个 i 和 i' 都是变量**，它们这个式子非常优美，可以**直接消掉**。
我们接下来看，就是说i 加 gap 和 i 加 gap 减一这两个环是否会有相同的情况。
如上图所示，无非其实就是两种相同的情况嘛。
那么另外一种情况就是有可能成立的了。也就是二 gap 减一，和百分之 n，mod n 是零。
```cpp
void Solve() {
ll L,R;
cin >> L >> R;
ll N=L+R;
// 就是 L
ll gap1=(L+1)-1;
ll ans1=N;
// 如果是这个重复了，由于与这个 i 无关，因此所有 i 都有相同，总个数就是 N/2
if (2*gap1%N==0) {
ans1=N/2;
}
ll gap2=gap1-1;
ll ans2=N;
if (2*gap2%N==0) {
ans2=N/2;
}
// 相同情况处理
if ((gap1+gap2)%N==0) {
ans2=0;
}
cout<<ans1+ans2<<"\n";
}
```
## AC代码
AC
[https://qoj.ac/submission/2027025](https://qoj.ac/submission/2027025)
::: 源代码
```cpp
/**
* Problem: Around the Table
* Contest: QOJ
* Judge: Virtual Judge
* URL: https://vjudge.net/problem/QOJ-14560
* Created: 2026-02-11 12:20:26
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll L,R;
cin >> L >> R;
ll N=L+R;
// 就是 L
ll gap1=(L+1)-1;
ll ans1=N;
if (2*gap1%N==0) {
ans1=N/2;
}
ll gap2=gap1-1;
ll ans2=N;
if (2*gap2%N==0) {
ans2=N/2;
}
if ((gap1+gap2)%N==0) {
ans2=0;
}
cout<<ans1+ans2<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://qoj.ac/submission/2027025
*/
```
:::
## 心路历程（WA，TLE，MLE……）