「DROI」Round 1 游戏

GitHub 跳转原题关系图返回列表

前 k 轮已经能区分所有 x，当且仅当前缀询问的 lcm 等于 lcm(1..n)，因此答案就是所有必需质数最高幂第一次被覆盖轮次的最大值。

OJ: luogu

题目 ID: P8980

难度:提高+/省选-

标签:数论最大公约数质因数分解推导

日期: 2026-06-21 00:29

题意

你先选一个 x (1<=x<=n)。

之后第 i 轮会被问到一个 a_i，你要回答 gcd(x,a_i)。

如果小朋友根据前若干轮答案已经能唯一确定 x，游戏就在那一轮结束。

要求你把 x 选得尽量“难猜”，使游戏结束得最晚；若一直无法唯一确定，则输出 game won't stop。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解。
// 直接枚举 x，再模拟每轮后还有哪些候选数与它回答完全一致。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, Q;
        cin >> n >> Q;
        vector<int> a(Q + 1);
        for (int i = 1; i <= Q; i++) {
            cin >> a[i];
        }

        bool never_stop = false;
        int best = 1;

        for (int x = 1; x <= n; x++) {
            vector<int> cand;
            for (int y = 1; y <= n; y++) {
                cand.push_back(y);
            }

            int stop_round = Q + 1;

            for (int i = 1; i <= Q; i++) {
                int gx = gcd(x, a[i]);
                vector<int> next_cand;
                for (int y : cand) {
                    if (gcd(y, a[i]) == gx) {
                        next_cand.push_back(y);
                    }
                }
                cand.swap(next_cand);
                if ((int) cand.size() == 1) {
                    stop_round = i;
                    break;
                }
            }

            if (stop_round == Q + 1) {
                never_stop = true;
                break;
            }
            best = max(best, stop_round);
        }

        if (never_stop) {
            cout << "game won't stop\n";
        } else {
            cout << best << '\n';
        }
    }

    return 0;
}

brute.cpp 会直接枚举 x，并维护当前还有哪些候选数和它回答一致，只适合小数据。

正式解的核心结论是：

前 k 轮已经能区分 1..n 中所有数
当且仅当
lcm(a_1,...,a_k) = lcm(1,2,...,n)。

原因在于 gcd 只能观察质因子指数，而且会被询问数 a_i 的质因子指数截断。

如果某个必需的最高幂 p^e 从未出现在前缀询问的 lcm 中，那么“是否拥有这层最高幂”就无法被看出来，至少会留下两个不同的候选数。

反过来，只要所有必需的最高幂都被覆盖了，那么每个数的质因数分解信息都能被完全识别，所有 x 也就都被区分开了。

于是答案就很直接：

对每个必需质数 p
记录它第一次达到所需指数的轮次
最后取这些轮次的最大值

如果有某个必需质数直到最后也没被覆盖，答案就是：

game won't stop

代码

cpp

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185#include <bits/stdc++.h>
using namespace std;

const int HARD_N = 32465962;

struct FastScanner {
    static const int BUFSIZE = 1 << 20;
    int idx, size;
    char buf[BUFSIZE];

    FastScanner() {
        idx = 0;
        size = 0;
    }

    inline char getch() {
        if (idx >= size) {
            size = (int) fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) {
                return 0;
            }
        }
        return buf[idx++];
    }

    template <class T>
    bool read_unsigned(T &x) {
        x = 0;
        char ch = getch();
        while (ch != 0 && (ch < '0' || ch > '9')) {
            ch = getch();
        }
        if (ch == 0) {
            return false;
        }
        while (ch >= '0' && ch <= '9') {
            x = x * 10 + (ch - '0');
            ch = getch();
        }
        return true;
    }
} scanner;

int spf[HARD_N + 1];
vector<int> primes;
int first_pos[HARD_N + 1];

void build_sieve() {
    primes.reserve(2100000);
    for (int i = 2; i <= HARD_N; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; j < (int) primes.size(); j++) {
            int p = primes[j];
            long long v = 1LL * i * p;
            if (v > HARD_N) {
                break;
            }
            spf[v] = p;
            if (p == spf[i]) {
                break;
            }
        }
    }
}

int need_exp_for_prime(int p, int n) {
    int exp = 1;
    long long cur = p;
    while (cur * p <= n) {
        cur *= p;
        exp++;
    }
    return exp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    build_sieve();

    unsigned int T;
    scanner.read_unsigned(T);

    vector<int> touched;
    touched.reserve(100000);

    for (unsigned int tc = 0; tc < T; tc++) {
        unsigned long long n64;
        unsigned int Q;
        scanner.read_unsigned(n64);
        scanner.read_unsigned(Q);

        // n=1 时，小朋友第一轮后一定已经能唯一确定。
        if (n64 == 1) {
            unsigned long long tmp;
            for (unsigned int i = 0; i < Q; i++) {
                scanner.read_unsigned(tmp);
            }
            cout << 1 << '\n';
            continue;
        }

        bool impossible = false;

        // 对于 p > sqrt(n) 的质数，所需指数只能是 1。
        // 每个 a_i <= n 最多只能包含一个这样的质数。
        // 因此如果这类质数个数已经大于 Q，则不可能全部覆盖。
        if (n64 > HARD_N) {
            impossible = true;
        }

        int n = 0;
        if (!impossible) {
            n = (int) n64;
            int large_prime_count =
                (int) (upper_bound(primes.begin(), primes.end(), n) -
                       upper_bound(primes.begin(), primes.end(), (int) sqrt((long double) n)));
            if (large_prime_count > (int) Q) {
                impossible = true;
            }
        }

        for (unsigned int i = 1; i <= Q; i++) {
            unsigned long long a64;
            scanner.read_unsigned(a64);

            if (impossible) {
                continue;
            }

            int x = (int) a64;
            while (x > 1) {
                int p = spf[x];
                int cnt = 0;
                while (x % p == 0) {
                    x /= p;
                    cnt++;
                }

                int need = need_exp_for_prime(p, n);
                if (cnt >= need && first_pos[p] == 0) {
                    first_pos[p] = (int) i;
                    touched.push_back(p);
                }
            }
        }

        if (impossible) {
            cout << "game won't stop\n";
            continue;
        }

        int ans = 1;
        int limit = (int) (upper_bound(primes.begin(), primes.end(), n) - primes.begin());

        for (int i = 0; i < limit; i++) {
            int p = primes[i];
            if (first_pos[p] == 0) {
                impossible = true;
                break;
            }
            if (first_pos[p] > ans) {
                ans = first_pos[p];
            }
        }

        if (impossible) {
            cout << "game won't stop\n";
        } else {
            cout << ans << '\n';
        }

        for (int p : touched) {
            first_pos[p] = 0;
        }
        touched.clear();
    }

    return 0;
}

复杂度

预处理一次筛表后，主过程只需要对所有询问做质因数分解。

整体复杂度由分解总量决定，可以通过本题数据。

总结

这题表面上在找一个“最难猜的 x”，其实根本不需要枚举 x。

真正要判断的是：

前缀询问的 lcm 是否已经覆盖了 1..n 所需的全部质数最高幂

一旦想到这一点，整题就变成了一个很简洁的数论覆盖问题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8980 「DROI」Round 1 游戏

题目背景

人生，又何尝不是一场游戏呢？

题目描述

你将和一名小朋友进行 $T$ 次游戏，每一次游戏的规则如下：

首先，你需要在 $[1,n]$ 中选择一个正整数 $x$ 。
接下来，小朋友会有 $Q$ 次询问，对于每次询问，他会给出一个 $a_i$ （保证 $a_i \in [1,n]$ ），你需要回答他 $\gcd(x,a_i)$ 的值。
当某一轮小朋友得到答案后，如果他能唯一确定你选择的数，那么本次游戏结束。

现在你提前知道了小朋友每次询问的 $a_i$ ，你需要找到一个 $x$ ，使得游戏持续的轮数最长。

输入格式

本题有多组数据。

第一行一个整数 $T$ ，表示进行游戏的次数。

对于每次游戏：

第一行两个整数，分别为 $n$ 和 $Q$ 。

第二行 $Q$ 个整数，其中第 $i$ 个整数表示 $a_i$ 。

输出格式

对于每次游戏，请输出游戏能持续的最长轮数，如果存在一个 $x$ 使得小朋友在 $Q$ 轮之后也无法唯一确定其值，则输出game won't stop。

输入输出样例 #1

输入 #1

text

输出 #1

text

1game won't stop

输入输出样例 #2

输入 #2

text

1
2
3
4
52
8 5
8 2 3 5 7 
24 16
3 17 18 5 19 4 16 23 7 11 13 18 6 21 22 2

输出 #2

text

1
25
11

说明/提示

样例解释#1

选取 $11$ 作为 $x$ ，显然小朋友到游戏结束也无法唯一确定。

样例解释#2

对于第一组数据：选取 $1$ 作为 $x$ ，小朋友在第五轮结束后可以唯一确定 $x$ ，可以证明不存在更优的 $x$ 。

对于第二组数据：同理，选取 $1$ 作为 $x$ 即可。

数据范围

「本题采用捆绑测试」

$\operatorname{Subtask} 1(20\%)$ ： $n,Q\leq 500$ 。
$\operatorname{Subtask} 2(20\%)$ ： $n,Q \leq 5 \times 10^4$ 。
$\operatorname{Subtask} 3(30\%)$ ： $Q \leq 10^5$ 。
$\operatorname{Subtask} 4(30\%)$ ：无特殊限制。

对于 $100\%$ 的数据： $T \leq 10$ ， $1 \leq a_i \leq n \leq 10^{18}$ ， $1 \leq Q \leq 2\times 10^{6}$ ， $\sum Q \leq 6\times 10^{6}$ 。

本题输入量较大，请用较快的输入方法。

「DROI」Round 1 游戏

目录

题意

思路

代码

复杂度

总结

一图流解析