The 2025 ICPC 德国 German Collegiate Programming Contest——A. Around the Table

题目大意

题目名称：Around the Table

题意总结：
公园里有一张乒乓球桌，初始时左边队列有 $\ell$ 个人，右边队列有 $r$ 个人。左边队首的人先持球。
游戏规则如下：

持球者将球打到对面，然后立刻跑到对面队列的队尾。
对面队首的人接球后成为新的持球者，重复上述过程。
假设游戏进行无限次（ $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 是一个无序对。

A 对 D（记录组合 {A, D}）。A 击球后去右边队尾。局面变更为：左 [B]，右 [D, E, A]。
B 对 D（记录组合 {B, D}）。D 击球后去左边队尾。局面变更为：左 [B, D]，右 [E, A]。
B 对 E（记录组合 {B, E}）。B 击球后去右边队尾。局面变更为：左 [D]，右 [E, A, B]。
D 对 E（记录组合 {D, E}）。E 击球后去左边队尾。局面变更为：左 [D, E]，右 [A, B]。
D 对 A（组合 {A, D} 已存在）。D 击球后去右边队尾。局面变更为：左 [E]，右 [A, B, D]。
E 对 A（记录组合 {E, A}）。A 击球后去左边队尾。局面变更为：左 [E, A]，右 [B, D]。
E 对 B（组合 {B, E} 已存在）。E 击球后去右边队尾。局面变更为：左 [A]，右 [B, D, E]。
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$ 什么时候相等（此时两类配对产生的是同一个集合，不能重复计数）。

这三层提示应该足够你推出最终公式了。要继续深入还是先自己想一下？

_______________[ 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

我们还是把第一个数字给反转一下吧，把第一个数字反转一下更加符更加符合我们人类的这个直觉。

你会发现一二三四五，这样子是轮流出现的，是轮流出现的，就像模运算一样。

_______________[ 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' \\

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 是零。

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

源代码

/**
 * 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

*/

Znzryb's Blog

The 2025 ICPC 德国 German Collegiate Programming Contest——A. Around the Table

题目大意

思路讲解

好的，你还没有开始写。这道题其实有很漂亮的结构，我来给你一些分层提示，你可以看一个想一下，不够再往下看。

AC代码

心路历程（WA，TLE，MLE……）