形式化题目

给定两个正多边形：多边形 A 边长为 $A$，有 $M$ 条边；多边形 B 边长为 $B$，有 $N$ 条边。 初始时它们有一条公共边重合并对齐。A 在 B 的外沿顺时针进行无滑动的滚动。 求多边形 A 至少要发生多少次“旋转”，才能使得 A 在整体上又完整对齐在 B 的最开始的那条边上。 一次旋转定义为：A 绕某个与 B 接触的端点转动，直到其下一条边接触到 B 的某条边，或是被 B 的凸角截断发生支点切换。

多组测试数据。 数据范围：$1 \le A \le B \le 10^6$，$3 \le M, N \le 10^6$。

正解

思路

这是一道经典的数学模型转化题。

首先，多边形 A 究竟什么时候才算作“回到原位置”？ 由于正多边形具有完全的旋转对称性（所有的边和角完全等价），题目中的“回到原位置”并不要求 A 必须是某个特定的端点贴合原位，只要 A 的任意一条边整条贴合在 B 的起始边上，它的状态就和最开始一模一样。因此，变量 $M$（多边形 A 的边数）对本题答案完全没有影响。

我们可以把 A 在 B 外围滚动的过程拉直：相当于把 B 的边界拉直成一条总长度为 $N \times B$ 的直线，并且每隔 $B$ 的长度就存在一个向外弯折的“凸角”。 同样，A 的单次滚动步长为 $A$。要让 A 回到原位，它在 B 表面走过的总距离 $X$ 必须既是 A 的边长的倍数，又是 B 的总周长的倍数。因此，滚动的总长度为：

在这段总长度为 $X$ 的行程中，A 发生旋转的总次数可以理解为发生“事件”的次数。有两种情况会触发旋转：

1. A 走完了一条完整的边长 $A$，前端点落下进行新的旋转。对应的事件位置为 $(0, X]$ 中所有 $A$ 的倍数。
2. A 在延伸时，碰到了 B 的凸角（因为 B 有拐角，A 被迫在此截断并改变旋转中心）。对应的事件位置为 $(0, X]$ 中所有 $B$ 的倍数。

若 A 的端点恰好和 B 的凸角重合（即该位置既是 $A$ 的倍数也是 $B$ 的倍数），此时 A 顺理成章地绕此点旋转，不会发生两次截断动作，重合只算一次。

因此，旋转次数等于 $(0, X]$ 区间内 $A$ 的倍数点与 $B$ 的倍数点构成的集合大小。利用容斥原理，答案为：

这便是最终的数学解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 22:30
# update_at: 2026-10-10 00:05

import math
import sys


def solve() -> None:
    """多组数据读到 EOF，每组 A M B N，输出 A 绕 B 滚动回原位所需的旋转次数。

    把 B 的边界拉直成总长 N*B 的线段（每隔 B 有一个拐角），A 每走完一条边 A
    旋转一次、每碰到一个拐角也多旋转一次，两时刻重合只算一次
    ⇒ 答案 = (0, X] 内「A 的倍数或 B 的倍数」的个数，X = lcm(A, N*B)。
    """
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    # 四份引用共用同一个迭代器，每组正好吃掉 4 个；末尾不足一组则整组丢弃，
    # 与官方 std.cpp 的 while (cin >> a >> m >> b >> n) 行为一致。m 只消费不参与计算。
    for a, m, b, n in zip(data, data, data, data):
        nb = n * b
        x = a // math.gcd(a, nb) * nb                   # x = lcm(a, n*b)：回到原位走过的总路程
        y = a // math.gcd(a, b) * b                     # y = lcm(a, b)
        ans = x // a + x // y * (y // b - 1)            # 容斥：A 的倍数 ∪ B 的倍数 的个数
        out.append(str(ans))

    if out:
        print('\n'.join(out))


if __name__ == '__main__':
    solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 22:30
 * update_at: 2026-10-10 00:05
 */
// main.cpp：卡片。
//   把 B 的边界拉直成一条总长 N*B 的线段，每隔 B 有一个向外的拐角。
//   Alice 每走完一条边长 A 要旋转一次，碰到 B 的拐角也要多旋转一次；
//   两种时刻重合时只算一次 ⇒ 旋转次数 = (0, X] 内「A 的倍数或 B 的倍数」的个数，
//   其中回到原位所需的总路程 X = lcm(A, N*B)。（由正多边形的旋转对称性，
//   只要 A 的整条边重新贴回起始边就算回到原位，故 A 的边数 M 不影响答案。）
//   容斥：ans = X/A + X/B - X/lcm(A,B)。这里把后两项合并成 (X/lcm(A,B))*(lcm(A,B)/B - 1)。
// 多组测试数据，while 读到 EOF，每组输出一行。
#include <iostream>
#include <numeric>

using namespace std;

typedef long long ll;

void solve() {
    ll a, m, b, n; // m 只读入、不参与计算：正多边形对称，A 的边数 M 与答案无关
    while (cin >> a >> m >> b >> n) {
        ll nb = n * b;
        ll x = a / std::gcd(a, nb) * nb; // x = lcm(a, n*b)，先除后乘避免中间乘积溢出
        ll c1 = x / a;                   // (0, x] 中 A 的倍数个数
        ll y = a / std::gcd(a, b) * b;   // y = lcm(a, b)
        ll c2 = x / y * (y / b - 1);     // (0, x] 中 B 的倍数个数去掉与 A 的倍数重合的部分
        cout << c1 + c2 << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

• 时间复杂度：单次询问的复杂度取决于求最大公约数 gcd 的消耗，即 $\mathcal{O}(\log(\min(A, N \times B)))$。对于多组查询均能轻松通过。
• 空间复杂度：$\mathcal{O}(1)$。

总结

本题的验证依赖与官方参考代码（std.cpp）及异源程序的交叉验证。基于详细的大规模对拍，我们得出以下结论：

1. 核心算法验证与等价性 容斥公式 Ans = X/A + X/B - X/lcm(A, B) 经过 $216,000$ 组恒等式检验（在 $A, B \le 60$ 的组合内）与官方 c1 + c2 分块算法完全等效，分歧为 0。
2. 多测到 EOF 是承重约定 尽管题面描述为“一行，四个整数”，但实际为多组数据读入直到 EOF。若只读一组（变异 V1a），在所有 $20736$ 组穷举测试中将失败 $20735$ 组，样例也会在第二组直接错掉。最小复现：printf '2 4 3 4\n3 4 4 4\n' | ./main 应当输出 8 24，改成单次读入则会丢失第二个答案。
3. M 变量完全不参与计算 对拍证明：固定 $A,B,N$，改变 $M$（$6 \times 63$ 组测试）输出恒定不变。且让 $M$ 参与计算的三个变异公式（C8、C9、C10）在包含样例 1 与样例 3 的测试中全部直接错误。这从数据表现和代数逻辑上均坐实了“$M$ 无效”并非 bug，而是题面本身的迷惑项。
4. 溢出防范（V1b 不承重 vs V1f 承重）
   • V1b (先乘后除计算 $X$) 不承重：因为 $a \times (n \times b) \le 10^6 \times (10^6 \times 10^6) = 10^{18}$，完全在 long long 的安全范围内（$9.22 \times 10^{18}$），即便直接写 a * n * b / gcd 也不会溢出（穷举 0 失败、50万压测 0 失败），不必宣称先除后乘对计算 $X$ 是防溢出的必要操作。
   • V1f (先乘后除计算 $c2$) 真溢出：若将 c2 计算改为 c2 = x * (y / b - 1) / y，则在边界、大数以及 50 万压测中产生严重失败。原因是中间量可达 $\approx 10^{24}$（80 bit），必定溢出 long long。最小复现输入：999983 3 999984 1000 将因溢出输出错误值 1003808947，而正确结果为 1999966000。
5. 候选策略（V8）区分度 不包含容斥项的变异（C2, C3, C4, C7）在测试中均无法被区分（同等失败 20736 次），这意味着题面数据规模未充分分层。而带有 $M$ 的 C8/C9/C10 策略直接被样例排除。
6. 证据强度声明 由于本题无官方 .in/.out 真实测试数据文件，验证属于“四方互相一致”（main.cpp、main.py、官方 std.cpp、无公式推导的纯事件步进模拟和集合统计的 Python 脚本 brute_set.py）。 测试规模包括：$20736$ 组穷举（变量 $\in [1,12]$）、$7805$ 组结构与边界测试、$3009$ 组百万级大数随机、$500,000$ 组压力测试，四方输出完全一致。
7. T9 规范化检查项
   • 数据范围约束：$A, B \le 10^6$，$N \le 10^6$ 且 $A \le B$。
   • 极值边界：注意 $N \times B$ 最大为 $10^{12}$，中间步骤求得的 $X$ 最大在 $10^{18}$ 左右。
   • 变量类型：必须使用 64 位整型（long long）。
   • 多测：隐藏条件，必须以 EOF 为终止判定。
   • 输出格式：无多余空格要求。