LOJ #10041「一本通 2.1 练习 7」门票 题解

题目大意：

给定一个数列 \({a_n},a_0=1,a_{i+1}=(A\times a_i+a_i\bmod B)\bmod C\)，求这个数列第一次出现重复的项的标号。

Sol：

哈希表模板题。
模数随便设，\(2000003\) 实际效果比较好，跑得挺快。
每次计算一下数列里新的项的值，插入到哈希表里。同时再判断是否重复。
有一个小坑，就是第一项的 \(1\) 也要插入进去。

Code：

#include <bits/stdc++.h>
using namespace std;
const int maxN = 2000005;
#define int long long
#define P 2000003
struct node {
    int v, nxt;
}rec[maxN];
int A, B, C, hd[maxN];
namespace HASH {
    int tot;
    int H(int x) {
        return x%P;
    }
    bool add(int x, int v) {
        for(int i = hd[x]; i; i = rec[i].nxt)
            if(rec[i].v == v) return true;
        rec[++tot].v = v;
        rec[tot].nxt = hd[x];
        hd[x] = tot;
        return false;
    }
}
using HASH::H;
using HASH::add;
signed main() {
    freopen("ticket.in", "r", stdin);
    freopen("ticket.out", "w", stdout);
    cin >> A >> B >> C;
    int x = 1;
    add(1, 1);
    for(int i = 1; i <= 2000000; i++) {
        x = (x*A+x%B)%C;
        if(add(H(x), x)) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

LOJ #10041「一本通 2.1 练习 7」门票 题解

原文：https://www.cnblogs.com/Xray-luogu/p/11569669.html