题目地址：洛谷：【P3306】[SDOI2013]随机数生成器 – 洛谷、BZOJ：Problem 3122. — [Sdoi2013]随机数生成器

题目描述

小W喜欢读书，尤其喜欢读《约翰克里斯朵夫》。最近小W准备读一本新书，这本书一共有P页，页码范围为0..P-1。
小W很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用NOI2012上学习的线性同余法生成一个序列，来决定每天具体读哪一页。
我们用Xi来表示通过这种方法生成出来的第i个数，也即小W第i天会读哪一页。这个方法需要设置3个参数a,b,X1，满足0<=a,b,X1<=p-1，且a,b,X1都是整数。按照下面的公式生成出来一系列的整数：Xi+1=(aXi+b) mod p其中mod表示取余操作。
但是这种方法可能导致某两天读的页码一样。
小W要读这本书的第t页，所以他想知道最早在哪一天能读到第t页，或者指出他永远不会读到第t页。

输入输出格式

输入格式：
输入含有多组数据，第一行一个正整数T，表示这个测试点内的数据组数。 接下来T行，每行有五个整数p，a，b，X1，t，表示一组数据。保证X1和t都是合法的页码。 注意：P一定为质数

输出格式：
共T行，每行一个整数表示他最早读到第t页是哪一天。如果他永远不会读到第t页，输出-1。

输入输出样例

输入样例#1：

3
7  1 1 3 3
7  2 2 2 0
7  2 2 2 1

输出样例#1：

1 
3 
-1

说明

0<=a<=P-1,0<=b<=P-1,2<=P<=10^9

题解

本题需要的数学姿势有：BSGS算法（大步小步法）及其扩展原理及应用 | KSkun’s Blog
咦这个题好像能推式子。
首先X_1 \equiv t \pmod{p}的时候答案直接就是1。
然后考虑一下X_i的通项其实就是底下这个
X_i = [a^{i-1}X_1 + b(1 + a + \cdots + a^{i-2})] \bmod p
那也就是说我要求使下面这个成立的最小的i。
a^{i-1}X_1 + b(1 + a + \cdots + a^{i-2}) \equiv t \pmod{p}
用等比数列求和公式啊！
a^{i-1}X_1 + b \cdot \frac{1-a^{i-1}}{1-a} \equiv t \pmod{p}
乱搞一通
a^{i-1} \equiv \frac{t(1-a)-b}{X_1(1-a)-b} \pmod{p}
直接一个BSGS套上去。
诶还是全WA了？GG，开始拍。
噫漏了a=1的情况，来推一下a=1的情况
X_1 + b(i-1) \equiv t \pmod{p}
这个移项以后i就出来了。
等一下等一下，万一b=0呢？特判搞一搞。
再等一下，万一a=0呢？还得特判搞一搞。
这些写全了才能A。
吐槽：HashMap的模数改成19260817以后卡的飞起啊！

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline LL fpow(LL n, LL k, LL p) {
    LL res = 1;
    for(; k; n = n * n % p, k >>= 1) {
        if(k & 1) res = res * n % p;
    }
    return res;
}

const int MO = 611977, MAXN = 1000005;

struct HashMap {
    int head[MO + 5], key[MAXN], value[MAXN], nxt[MAXN], tot;
    inline void clear() {
        tot = 0;
        memset(head, -1, sizeof(head));
    }
    HashMap() {
        clear();
    }
    inline void insert(int k, int v) {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) {
                value[i] = v;
                return;
            }
        }
        key[tot] = k; value[tot] = v; nxt[tot] = head[idx]; head[idx] = tot++;
    }
    inline int operator[](const int &k) const {
        int idx = k % MO;
        for(int i = head[idx]; ~i; i = nxt[i]) {
            if(key[i] == k) return value[i];
        }
        return -1;
    }
} x;

inline LL bsgs(LL a, LL b, LL p) {
    if(b == 1) return 0;
    LL m = ceil(sqrt(p + 0.5)), inv = fpow(a, p - m - 1, p);
    x.clear();
    x.insert(1, 0);
    for(LL i = 1, e = 1; i < m; i++) {
        e = e * a % p;
        if(x[e] == -1) x.insert(e, i);
    }
    for(LL i = 0; i < m; i++) {
        if(x[b] != -1) {
            LL res = x[b];
            return i * m + res;
        }
        b = b * inv % p;
    }
    return -1;
}

LL T, p, a, b, x1, t;

int main() {
    T = readint();
    while(T--) {
        p = readint(); a = readint(); b = readint(); x1 = readint(); t = readint();
        if(x1 == t) {
            puts("1");
            continue;
        }
        if(a == 0) { // a=0特判
            if(b == t) puts("2");
            else puts("-1");
            continue;
        }
        if(a == 1) { // a=1特判
            LL res = (((t - x1) * fpow(b, p - 2, p) % p + 1) % p + p) % p;
            if(b == 0) puts("-1");
            else printf("%lld\n", res ? res : p);
            continue;
        }
        LL B = ((t * (1 - a) % p - b) % p + p) % p, BI = ((x1 * (1 - a) % p - b) % p + p) % p;
        B = B * fpow(BI, p - 2, p) % p;
        LL res = bsgs(a, B, p);
        printf("%lld\n", res == -1 ? -1 : res + 1);
    }
    return 0;
}