思路与算法

以相邻两项(a,b)为状态，转移到(b,(Xb+Ya+Z) mod P)。位集记录访问过的P²种状态，直到首次重复，并只保存命中特征值C的位置。回放至重复状态确定前周期mu，剩余为周期；区间答案用命中位置二分、完整周期次数和尾部命中数求两个前缀之差。

正确性说明

有限确定状态第一次重复后，未来序列必完全周期化，回放找到的mu是最早周期入口。状态第一坐标正是当天S_i，命中位置以0基记录，所以前days项的命中数可拆为前周期、完整周期及剩余段，二分lower_bound给出严格小于尾端的位置数，区间差正确。

复杂度

每组预处理O(P²)时间上界，位集初始化和空间O(P²/64)。命中位置最坏O(P²)宽松空间界；本模型Y非零时转移可逆，一周期内命中不超过P，Y=0退化一阶时周期最多P，因此实际命中存储O(P)。Q次查询O(QlogP)。

易错点

Y=0可能有前周期，不能直接假定从第1天循环。A、B也要参与计数。L,R可达10^18，周期乘次数及答案用无符号64位；状态索引最大P²-1，用位集而不是P²个64位时间戳。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using U = unsigned long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int A, B, X, Y, Z, P, C, Q;
        cin >> A >> B >> X >> Y >> Z >> P >> C >> Q;
        vector<unsigned long long> seen((P * P + 63) / 64);
        vector<int> hits;
        int a = A, b = B, len = 0;
        while (true) {
            int id = a * P + b;
            if (seen[id >> 6] >> (id & 63) & 1)
                break;
            seen[id >> 6] |= 1ULL << (id & 63);
            if (a == C)
                hits.push_back(len);
            int v = (X * b + Y * a + Z) % P;
            a = b;
            b = v;
            len++;
        }
        int ra = a, rb = b, mu = 0;
        a = A;
        b = B;
        while (a != ra || b != rb) {
            int v = (X * b + Y * a + Z) % P;
            a = b;
            b = v;
            mu++;
        }
        int period = len - mu;
        int pre = lower_bound(hits.begin(), hits.end(), mu) - hits.begin(), per = hits.size() - pre;
        auto cnt = [&](U days) -> U {
            if (days <= (U)mu)
                return lower_bound(hits.begin(), hits.end(), days) - hits.begin();
            U z = days - mu, cycles = z / period, rem = z % period;
            return pre + cycles * per +
                   (lower_bound(hits.begin() + pre, hits.end(), mu + rem) - (hits.begin() + pre));
        };
        while (Q--) {
            U l, r;
            cin >> l >> r;
            cout << cnt(r) - cnt(l - 1) << '\n';
        }
    }
}