【CSGRound1】天下第一

题意

有两个数 x、y 和模数 p。

游戏按下面的顺序进行：

第 1 回合：x = (x + y) mod p
第 2 回合：y = (x + y) mod p
第 3 回合：x = (x + y) mod p
第 4 回合：y = (x + y) mod p

如此反复。

如果 x 先变成 0，输出 1；如果 y 先变成 0，输出 2；如果永远不会出现 0，输出 error。

思路

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

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// brute.cpp：小数据直接模拟，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int t, p;

int brute_one(int x, int y) {
    x %= p;
    y %= p;

    set<tuple<int, int, int> > vis;
    int turn = 0;

    while (true) {
        tuple<int, int, int> state = make_tuple(x, y, turn);
        if (vis.count(state)) {
            return -1;
        }
        vis.insert(state);

        if (turn == 0) {
            x = (x + y) % p;
            if (x == 0) {
                return 1;
            }
        }
        else {
            y = (x + y) % p;
            if (y == 0) {
                return 2;
            }
        }

        turn ^= 1;
    }
}

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

    cin >> t >> p;
    while (t--) {
        int x, y;
        cin >> x >> y;
        int ret = brute_one(x, y);
        if (ret == -1) {
            cout << "error\n";
        }
        else {
            cout << ret << '\n';
        }
    }

    return 0;
}

如果直接按题目模拟，会发现新的数总是前两个数之和模 p。

于是我们可以定义：

a1 = x
a2 = y
a_n = (a_{n-1} + a_{n-2}) mod p

递推公式

把交替更新统一写成一个序列：

a_1=x,\quad a_2=y,\quad a_n=(a_{n-1}+a_{n-2})\bmod p

第 step 次操作得到的是 a_{step+2}。如果 step 为奇数，变成 0 的是 x；否则变成 0 的是 y。

那么：

第 1 次操作后，x = a3
第 2 次操作后，y = a4
第 3 次操作后，x = a5
第 4 次操作后，y = a6

也就是说，这个游戏本质上就是一条 Fibonacci 型递推数列。

所以问题变成：

看这条数列里第一次出现 0 的位置
如果出现在奇数次操作，对应 x 变成 0
如果出现在偶数次操作，对应 y 变成 0

接下来只差一个问题：会不会永远不出现 0，那要模拟多久？

这里用一个常见结论：

Fibonacci 数列模 p 一定会周期循环
它的周期长度不超过 6p

因此只要把一个完整周期扫完：

如果中途出现 0，就能立刻判断胜负
如果整个周期里都没出现 0，以后也不会出现，只能是 error

因为这题所有询问共用同一个 p，所以先预处理一次周期长度，再逐个询问扫描即可。

代码

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#include <bits/stdc++.h>
using namespace std;

int t, p;
int period_len;

// 预处理 Fibonacci 模 p 的周期长度。
void build_period() {
    if (p == 1) {
        period_len = 1;
        return;
    }

    int a = 0;
    int b = 1;
    period_len = 0;

    for (int i = 1; i <= 6 * p; i++) {
        int c = (a + b) % p;
        a = b;
        b = c;
        if (a == 0 && b == 1) {
            period_len = i;
            return;
        }
    }
}

// 返回 1 表示 x 先到 0，2 表示 y 先到 0，-1 表示平局。
int solve_one(int x, int y) {
    if (p == 1) {
        return 1;
    }

    x %= p;
    y %= p;

    // 令 a1 = x, a2 = y, 后面满足 a_n = a_{n-1} + a_{n-2} (mod p)。
    // 第 1 次操作得到 a3，对应 x；第 2 次操作得到 a4，对应 y。
    int a = x;
    int b = y;

    for (int step = 1; step <= period_len; step++) {
        int c = (a + b) % p;
        if (c == 0) {
            if (step & 1) {
                return 1;
            }
            return 2;
        }
        a = b;
        b = c;
    }

    return -1;
}

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

    cin >> t >> p;
    build_period();

    while (t--) {
        int x, y;
        cin >> x >> y;
        int ret = solve_one(x, y);
        if (ret == -1) {
            cout << "error\n";
        }
        else {
            cout << ret << '\n';
        }
    }

    return 0;
}

复杂度

预处理周期长度是 $O(p)$ ，更准确地说不超过 6p 步。

每个询问最多再扫一个周期，所以单次询问复杂度也是 $O(p)$ 。

总复杂度 $O(Tp)$ ，在 T <= 200、p <= 10000 的范围内完全可以通过。

总结

这题最关键的观察是：

交替更新其实没有本质区别，整体就是一个 Fibonacci 型递推
模 p 后序列一定会进入周期
所以不需要无限模拟，只要扫完一个周期即可

本质上是“递推 + 取模周期”的结合题。

【CSGRound1】天下第一

目录

题意

思路

递推公式

代码

复杂度

总结