P1965 [NOIP 2013 提高组] 转圈游戏 · 习题解析

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1965，日期见页头。两边不一致时信原站。

题目背景

NOIP2013 提高组 D1T1。

题目描述

n 个小伙伴（编号从 0 到 n−1）围坐一圈玩游戏。按照顺时针方向给 n 个位置编号，从 0 到 n−1。最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。

游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第 n − m 号位置上的小伙伴走到第 0 号位置，第 n − m + 1 号位置上的小伙伴走到第 1 号位置，……，第 n−1 号位置上的小伙伴顺时针走到第 m−1 号位置。

现在，一共进行了 10ᵏ 轮，请问 x 号小伙伴最后走到了第几号位置。

输入格式

共一行，包含四个整数 n, m, k, x，每两个整数之间用一个空格隔开。

输出格式

一个整数，表示 10ᵏ 轮后 x 号小伙伴所在的位置编号。

数据范围

对于 30% 的数据，0 < k < 7；
对于 80% 的数据，0 < k < 10⁷；
对于 100% 的数据，1 < n < 10⁶，0 < m < n，0 ≤ x ≤ n，0 < k < 10⁹。

时限 1 秒，内存 125 MB（128000 KB）。

输入输出样例

输入

10 3 4 5

输出

n = 10、m = 3、k = 4、x = 5 ⇒ 一共走 10⁴ = 10000 轮。

1★★★ 题面那三档，正好对应三种写法

★ 这道题最值钱的一件事，在数据范围那三行里

题面的档	对应的写法	顶格是多少
30%：`k < 7`	模拟每一轮（`x = (x+m) % n`，做 `10ᵏ` 次）	10⁶ 轮
80%：`k < 10⁷`	想到了公式，但 `10ᵏ mod n` 是连乘 `k` 次算的	10⁷ 次乘法
100%：`k < 10⁹`	★ 快速幂	30 次乘法

⇒ 出题人把三种写法各值多少分，直接写在题面上了。（「暴力值多少分」是「暴力 × 那道题分档」的属性的又一次 —— 而这一次三档一一对应，是本书见过最干净的一回。）

⚠ 注意 30% 档那个数：k < 7 说的是 k，而轮数是 10ᵏ ⇒ 最多 10⁶ 轮。到 80% 档 k < 10⁷ 时，轮数是 10^(10⁷) —— 光位数就有一千万位。 ⇒ 第 ① 版在那儿不是慢，是不可能。

p1965Brute.cpp第 ① 版：模拟每一轮 —— 参照物，稳拿 30 分

// 第 ① 版：老老实实模拟每一轮 —— 参照物，而且题面第一档就是给它的
//
// 「每轮第 i 号位置的人走到 i+m」⇒ 一轮就是 x = (x + m) % n，模拟 10^k 轮。
// ★ 题面写着「对于 30% 的数据，0 < k < 7」⇒ 最多 10⁶ 轮 ⇒ **它稳拿 30 分**。
// ⚠ 而 80% 档 k < 10⁷ ⇒ 轮数是 10^(10⁷)，**位数就有一千万位** —— 这一版在那儿不是慢，是不可能。
//
// ⇒ 为了不把页面挂死，这里给轮数封了顶（超过 10⁸ 直接打印 TOO_MANY）。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll n, m, k, x;
    if (scanf("%lld %lld %lld %lld", &n, &m, &k, &x) != 4) return 0;
    if (k > 8) { printf("TOO_MANY\n"); return 0; }      // 10^9 轮以上就别模拟了
    ll rounds = 1;
    for (ll i = 0; i < k; i++) rounds *= 10;
    ll pos = x % n;
    for (ll i = 0; i < rounds; i++) pos = (pos + m) % n;
    printf("%lld\n", pos);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

2★ 关键一步：把题目翻译成一个幂

★★ 两行推导，剩下的全是这一章的模板

每一轮，位置 x 的人走到 (x + m) mod n ⇒ 一轮就是加一个 m。

⇒ 走 R 轮就是加 R 个 m：终点 = (x + m·R) mod n。

题目问的 R = 10ᵏ ⇒ 只要算出 10ᵏ mod n，剩下是一次乘法、一次加法。

⇒ ★ 这道题真正考的是这两行；10ᵏ mod n 只是第 42 章那五行原样抄一遍。

p1965Loop.cpp⚠ 第 ② 版：公式对了，但 10ᵏ mod n 是连乘 k 次 —— 稳拿 80 分

p1965.cpp★ 正解：把连乘换成快速幂 —— AC

// P1965 转圈游戏 —— 正解：把题目翻译成一个幂，然后快速幂
//
// ★★ 关键一步全在纸上，不在代码里：
//   每一轮，位置 x 的小伙伴走到 (x + m) mod n ⇒ **一轮就是加一个 m**。
//   走 R 轮就是加 R 个 m ⇒ 终点 = (x + m·R) mod n。
//   而题目问的 R = 10^k ⇒ **只要算出 10^k mod n**，剩下的是一次乘法一次加法。
//
// ⇒ 10^k mod n 就是这一章的五行快速幂。O(log k)。
//
// ⚠ 两处必须 long long：
//   ① 快速幂内部 res * a：n < 10⁶ ⇒ 最大 (10⁶−1)² ≈ 10¹²，撑破 int；
//   ② m · (10^k mod n)：两个都 < 10⁶ ⇒ 同样 ≈ 10¹²。
//   （[本章第 5 步](/ch/42-fastpow/)那条线：模数 p 要 ≤ 3.04×10⁹ 才够 long long，这里 10⁶ 绰绰有余。）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static ll qpow(ll a, ll b, ll p) {
    ll res = 1 % p;                 // ★ 不是 1（本章第 5 步 ③）—— 这道题 n > 1，所以它其实用不上
    a %= p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    ll n, m, k, x;
    if (scanf("%lld %lld %lld %lld", &n, &m, &k, &x) != 4) return 0;
    ll r = qpow(10, k, n);          // 10^k mod n
    printf("%lld\n", (x + m % n * r) % n);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 三种写法在各自顶格上的秒表（独占实测，3 次取中位数；时限 1000 ms）

写法	顶格	本机	交上去
① 模拟 10ᵏ 轮	`k = 6`（30% 档）⇒ 10⁶ 轮	约 5 毫秒	30 分
② 连乘 `k` 次	`k = 10⁷`（80% 档）	约 50 毫秒	80 分
② 连乘 `k` 次	`k = 10⁹`（100% 档，外推）	★ 约 5.1 秒	✗ TLE（超 5 倍）
★ ③ 快速幂	`k = 10⁹`	★ 约 0.15 微秒	★ AC

★ 第 ③ 行和第 ④ 行的比值是 三十多万倍 —— 而两行的输入一模一样。

⚠⚠ 顺带一条量的时候自己踩的：这张表第一版把模数写成了 const ll N = 999983 （编译期常量）⇒ -O2 把 % N 换成了一次乘法加移位，四个数全部偏快（快速幂那格量到 0.07 微秒）。真程序的 n 是 scanf 读进来的 ⇒ 度量程序里那三个数改成了运行期才知道的值。 ⇒ ★★ 拿编译期常量当模数去量取模的秒表，量到的是编译器替你省掉的那一版。

3⚠ 三个错法 —— 而官方样例只挡得住一个

p1965Rounds.cpp✗ 错法一：把「10ᵏ 轮」读成了「k 轮」

p1965NoMul.cpp✗ 错法二：算出 10ᵏ mod n 之后忘了乘 m

p1965Int.cpp✗ 错法三：全用 int —— 两处乘法都撑得破

★★★ 官方样例的 n 正好是 10，而底数也是 10 —— 它对错法二完全没有区分度

样例 10 3 4 5：

版本	输出	挡住了吗
正解	5
✗ 把轮数读成 `k`	7	★ 挡住
✗ 忘了乘 `m`	5	✗ 放过
✗ 全用 `int`	5	✗ 放过

为什么错法二在样例上一个字都不会错：样例的 n = 10，而要算的是 10ᵏ mod n —— k ≥ 1 时 10ᵏ ≡ 0 (mod 10) ⇒ 乘不乘 m 都是 0，两版都输出 x。

⇒ 「它过了样例」的第三种原因：这组样例在结构上问不出这个问题 —— ⚠ 而这一次的巧合特别刺眼：题目里的底数是 10，而样例的 n 也是 10。

p1965Gen.cpp生成器（四档：顺手写的 / 大 n / n 是 10 的幂 / 顶格 k）

★★★ 四个档、三个错法，「满足触发条件」和「真被抓」十二格全部一个不差

档位（每档 300 轮）	✗ 读成 k 轮	✗ 忘了乘 m	✗ 全用 int	（int 会溢出的轮数）
0 顺手写的（`n ≤ 100`、`k ≤ 4`）	272	244	★ 精确的 0	0
1 大 `n`（`5×10⁵ ~ 10⁶`）、`k ≤ 4`	300	300	45	★ 45
⚠⚠ 2 `n` 是 10 的幂且 `k ≥ 指数`	296	★ 精确的 0	0	0
3 顶格 `k`（`< 10⁹`）	300	300	287	★ 287

★★ 两个「精确的 0」都能证，而且证明就是那一档的定义：

档 0 的 int：n ≤ 100 ⇒ 每一步乘法都 ≤ 10⁴，离 2³¹ 差七个数量级；
档 2 的忘了乘 m：n = 10ʲ 且 k ≥ j ⇒ 10ᵏ mod n = 0 ⇒ 乘不乘都一样（度量程序把这一档「10ᵏ ≡ 0 的轮数」数出来是 300 / 300）。

⚠⚠ 而档 2 是我第一版没造对的：只写了「n 取 10 的幂」，忘了还要 k ≥ 那个指数 —— n = 10⁴ 配 k = 1 时 10ᵏ mod n = 10 ≠ 0，那一档实测被抓 109 / 300，根本不是 0。 ⇒ ★★ 「结构性的 0」是要把那个结构写全了才成立的，写一半就成了「概率低」。

★ 顺带一条题面细节：数据范围写的是 0 ≤ x ≤ n（闭区间） —— x 真的可以等于 n（生成器四档里各出现 17 / 0 / 16 / 0 轮）。正解那句 (x + …) % n 顺手就把它盖住了，但读题时值得停一秒。

4★ 哪一版就已经能过了

p1965Count.cpp本页所有数字的出处

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

// P1965 的度量程序：./p1965Count csv        （本页的数字都出自它）
//
//   score : ★★★ 题面那三档**正好对应三种写法** —— 把每一档顶格量一遍，看谁在哪一档挂掉。
//   trig  : ★ int 溢出那个错法的**触发条件**（m·r 或 res·a 越过 2³¹）在各档里出现几轮。
//   zero  : ★ 档 2 那个「精确的 0」的证据：10^k mod n 恰好等于 0 的轮数。
//   xeqn  : ⚠ 题面写的是 **0 ≤ x ≤ n**（闭区间）—— 数一数生成器真造出 x == n 的轮数。
//
// ⚠ 这里**复刻**了 p1965Gen.cpp 的档位逻辑（同一个 mt19937、同一个种子公式）。
// ⚠ 秒表用 steady_clock 在进程内量，每档 3 次取中位数
//   （[第 12 章 P1923 那一跤](/sol/p1923/)：秒表断言的主语是余量，不是量级）。
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
typedef long long ll;

static ll qpow(ll a, ll b, ll p) {
    ll res = 1 % p; a %= p;
    while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; }
    return res;
}
static double med3(double a, double b, double c) { return max(min(a, b), min(max(a, b), c)); }

/** 复刻 p1965Gen.cpp */
static void gen(unsigned seed, int mode, ll& n, ll& m, ll& k, ll& x) {
    mt19937 rng(seed * 1000003u + 20260902u);
    if (mode == 0) { n = 2 + (ll)(rng() % 99u); k = 1 + (ll)(rng() % 4u); }
    else if (mode == 1) { n = 500000 + (ll)(rng() % 499999u); k = 1 + (ll)(rng() % 4u); }
    else if (mode == 2) {
        int j = 1 + (int)(rng() % 4u);
        n = 1; for (int t = 0; t < j; t++) n *= 10;
        k = j + (ll)(rng() % 4u);
    } else { n = 2 + (ll)(rng() % 999998u); k = 1 + (ll)(rng() % 999999999u); }
    m = 1 + (ll)(rng() % (unsigned)(n - 1));
    x = (ll)(rng() % (unsigned)(n + 1));
}

/** int 那一版会不会溢出：把它的每一步乘法都拿 long long 算一遍，看有没有越过 2³¹ */
static bool intOverflows(ll n, ll m, ll k) {
    const ll TOP = 2147483647LL;
    ll a = 10 % n, b = k, res = 1 % n;
    while (b) {
        if (b & 1) { if (res * a > TOP) return true; res = res * a % n; }
        if (a * a > TOP) return true;
        a = a * a % n;
        b >>= 1;
    }
    if (m % n * res > TOP) return true;
    return false;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    /* ① 四个档里：int 溢出的触发轮数 / 10^k ≡ 0 的轮数 / x == n 的轮数 */
    int trig[4] = {0, 0, 0, 0}, zero[4] = {0, 0, 0, 0}, xeqn[4] = {0, 0, 0, 0};
    for (int mode = 0; mode < 4; mode++)
        for (int s = 1; s <= 300; s++) {
            ll n, m, k, x; gen((unsigned)s, mode, n, m, k, x);
            if (intOverflows(n, m, k)) trig[mode]++;
            if (qpow(10, k, n) == 0) zero[mode]++;
            if (x == n) xeqn[mode]++;
        }

    /* ② 三档顶格 × 三种写法 */
    // ⚠⚠ 这三个**不能写成编译期常量**：`% N` 里的 N 一旦是常量，
    //   -O2 会把取模换成一次乘法 + 移位，量出来的秒数比真程序快好几倍
    //   （真程序的 n 是 scanf 读进来的）。第一版就中了这一招。
    static volatile ll VN = 999983, VM = 999979, VX = 12345;
    const ll N = VN, M = VM, X = VX;                 // 顶格形状（n 取一个接近 10⁶ 的质数）
    double msBrute30, msLoop80, msLoop100proj, usFast;
    {
        double t[3];
        for (int r = 0; r < 3; r++) {                // 30% 档顶格：k = 6 ⇒ 模拟 10⁶ 轮
            auto t0 = steady_clock::now();
            volatile ll pos = X % N;
            for (ll i = 0; i < 1000000; i++) pos = (pos + M) % N;
            t[r] = duration<double, milli>(steady_clock::now() - t0).count();
        }
        msBrute30 = med3(t[0], t[1], t[2]);
    }
    {
        double t[3];
        for (int r = 0; r < 3; r++) {                // 80% 档顶格：连乘 10⁷ 次
            auto t0 = steady_clock::now();
            volatile ll rr = 1 % N;
            for (ll i = 0; i < 9999999LL; i++) rr = rr * 10 % N;
            t[r] = duration<double, milli>(steady_clock::now() - t0).count();
        }
        msLoop80 = med3(t[0], t[1], t[2]);
    }
    {                                                // 100% 档：连乘 10⁸ 次再外推 ×10
        auto t0 = steady_clock::now();
        volatile ll rr = 1 % N;
        for (ll i = 0; i < 100000000LL; i++) rr = rr * 10 % N;
        double ms = duration<double, milli>(steady_clock::now() - t0).count();
        msLoop100proj = ms * 10.0;
    }
    {
        auto t0 = steady_clock::now();
        // ⚠ 指数每次都变一下：写成常数的话 qpow 是纯函数，-O2 会把它整个提到循环外
        //   （第一版就中了这一招，量出 0.07 微秒 —— 那是「一次都没跑」的意思）
        volatile ll acc = 0;
        for (int r = 0; r < 20000; r++) acc = acc + qpow(10, 999999999LL - r, N);
        usFast = duration<double, micro>(steady_clock::now() - t0).count() / 20000.0;
    }

    if (csv) {
        for (int i = 0; i < 4; i++) printf("trig%d,%d\n", i, trig[i]);
        for (int i = 0; i < 4; i++) printf("zero%d,%d\n", i, zero[i]);
        for (int i = 0; i < 4; i++) printf("xeqn%d,%d\n", i, xeqn[i]);
        printf("msBrute30,%.0f\n", msBrute30);
        printf("msLoop80,%.0f\n", msLoop80);
        printf("msLoop100proj,%.0f\n", msLoop100proj);
        printf("usFast,%.2f\n", usFast);
        printf("loop100OverLimit,%.1f\n", msLoop100proj / 1000.0);
        printf("fastOverLoop80,%.0f\n", msLoop80 * 1000.0 / usFast);
        return 0;
    }
    const char* NAME[4] = {"顺手写的（n ≤ 100、k ≤ 4）", "大 n（5×10⁵ ~ 10⁶）", "n = 10 的幂且 k ≥ 指数", "顶格 k"};
    printf("① 四个档各 300 轮\n");
    for (int i = 0; i < 4; i++)
        printf("   档 %d %-26s int 会溢出 %3d 轮 ／ 10^k ≡ 0 的 %3d 轮 ／ x == n 的 %2d 轮\n",
               i, NAME[i], trig[i], zero[i], xeqn[i]);
    printf("   ⇒ ★ 档 2 那一列的 300 就是「忘了乘 m」在那儿是**精确的 0** 的证明\n");
    printf("   ⚠ 而 x == n 真的会出现（题面写的是 0 ≤ x ≤ n，闭区间）\n");

    printf("\n② 题面三档 × 三种写法（独占实测，3 次取中位数；时限 1000 ms）\n");
    printf("   模拟 10^k 轮，k = 6（30%% 档顶格）      %.0f ms  ⇒ 稳拿 30 分\n", msBrute30);
    printf("   连乘 k 次，k = 10⁷（80%% 档顶格）       %.0f ms  ⇒ 稳拿 80 分\n", msLoop80);
    printf("   连乘 k 次，k = 10⁹（100%% 档，外推）    %.0f ms  ⇒ ✗ 超时 %.1f 倍\n",
           msLoop100proj, msLoop100proj / 1000.0);
    printf("   快速幂，k = 10⁹                         %.2f 微秒 ⇒ ★ AC（比连乘快 %.0f 倍）\n",
           usFast, msLoop80 * 1000.0 / usFast);
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

★ 只有第 ③ 版能拿满分 —— 而前两版分别值 30 和 80

这道题的价值不在算法（快速幂就是第 42 章那五行），而在两处：把题目翻译成一个幂那两行推导，以及读懂题面三档在说什么。

⚠ 而两个坑都和这一章的主题无关：一个是读题（10ᵏ 轮不是 k 轮），一个是第 42 章第 5 步那条老账（n < 10⁶ ⇒ 乘积到 10¹² ⇒ 必须 long long）。

洛谷 P1965 [NOIP 2013 提高组] 转圈游戏

0题目原文（本地存了一份）

输入

输出

1★★★ 题面那三档，正好对应三种写法

2★ 关键一步：把题目翻译成一个幂

3⚠ 三个错法 —— 而官方样例只挡得住一个

4★ 哪一版就已经能过了