门票

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 786 字

哈希表模拟数列记录首次重复下标

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1463
// 题意：给 A,B,C，数列 a_0=1、a_{i+1}=(A×a_i+a_i mod B) mod C，输出第一次出现重复项的标号，超过 2e6 输出 -1。
// 思路：直接模拟，哈希表记录每个数值首次出现的下标，一旦新项已在表中立即输出当前下标。
// 复杂度：O(min(答案,2e6)) 时间 / O(min(答案,2e6)) 空间
// 易错点：先算新项再查表，不能把自己算成重复；A×a_i 可达 1e18，中间量必须用 long long。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long A,B,C;
    if(!(cin>>A>>B>>C)) return 0;
    unordered_map<long long,int> pos;
    pos.reserve(2000005);
    pos.max_load_factor(0.7);
    long long a=1;
    pos[a]=0;
    const int LIM=2000000;
    for(int i=1;i<=LIM;i++){
        a=(A*a+a%B)%C;
        if(pos.count(a)){
            cout<<i<<'\n';
            return 0;
        }
        pos[a]=i;
    }
    cout<<-1<<'\n';
    return 0;
}

门票

正文

一本通·提高篇的其它内容