「一本通 2.1 练习 7」门票

题目描述

给定数列 ${a_n}$ ： $a_0=1$ ， $a_{i+1}=(A\times a_i + a_i\bmod B)\bmod C$ ，其中 $0\le A,B,C\le 10^9$ 。输入一行三个整数 $A,B,C$ ，输出该数列第一次出现重复项的标号，若该标号超过 $2\times10^6$ 则输出 $-1$ 。样例输入 2 2 9，样例输出 4。

思路

递推式是一个函数迭代，每项只由前一项决定，所以重复必然出现。从 $a_0=1$ 起逐项模拟，用哈希集合记录已经出现过的值，第一次撞上旧值的下标就是答案。值域 $C$ 可达 $10^9$ 开不下标记数组，但模拟步数不超过 $2\times10^6$ ，集合大小只与出现过的项数有关；注意 $a_0=1$ 也要先放进集合，且“超过 $2\times10^6$ ”不含恰好等于。

参考代码

Python 版：

python

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#!/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-09-30 12:24
# update_at: 2026-09-30 12:24

import sys

LIMIT = 2 * 10**6  # 题面规定：答案超过 2×10^6 输出 -1，所以最多往后模拟这么多项


def first_repeat(a: int, b: int, c: int) -> int:
    """返回数列第一次出现重复项的下标；若首次重复发生在 LIMIT 之后则返回 -1。"""
    value, seen = 1, {1}  # a_0 = 1；seen 是已经出现过的项的集合
    for i in range(1, LIMIT + 1):
        value = (a * value + value % b) % c
        if value in seen:
            return i  # value 之前出现过，i 就是第一次出现重复的标号
        seen.add(value)
    return -1


def solve() -> None:
    a, b, c = map(int, sys.stdin.buffer.read().split())
    print(first_repeat(a, b, c))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 00:12
 * update_at: 2026-10-06 00:12
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll LIMIT = 2000000; // 题目规定：答案超过 2×10^6 就输出 -1，所以最多模拟这么多项

ll A, B, C;

void solve() {
    // 数列是函数迭代，重复一定会出现；逐项模拟，第一次撞上旧值即答案。
    // 每项都在 [0, C) 内，但 C 可达 10^9 开不下标记数组；而模拟步数不超过 2×10^6，
    // 所以用哈希集合只登记真正出现过的值，集合大小与值域无关。
    unordered_set<ll> seen; // seen 记录已经出现过的项
    seen.reserve(LIMIT + 1);

    ll value = 1; // a_0 = 1，它也可能再次出现，必须先放进集合
    seen.insert(value);

    for (ll i = 1; i <= LIMIT; i++) {
        value = (A * value + value % B) % C;
        if (seen.count(value) != 0) {
            cout << i << '\n'; // value 之前出现过，标号 i 就是第一次出现重复的位置
            return;
        }
        seen.insert(value);
    }

    cout << -1 << '\n';
}

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

    cin >> A >> B >> C;
    solve();

    return 0;
}

「一本通 2.1 练习 7」门票

目录

题目描述

思路

参考代码