随机数生成器问题

解题思路：

第 $i$ 天观看第 $X_n = (aX_{n-1}+b)~mod~p$ 页，本题要求对于第 $t$ 页，找出最早看它的一页，也就是找到最小的 $n$ 使得 $X_n=t$。

由于本题的数据范围很大，因此不能直接枚举，那么我们就需要先对通项公式进行整理，对于 $mod~p$ 我们可以先提出来，先对于 $X_n=aX_{n-1}+b$ 进行处理。

我们设 $X_n+C=a(X_{n-1}+C)$ 和上式等价，解得 $C=\frac{b}{a-1}$，因此原方程等价于 $X_n+\frac{b}{a-1}=a(X_{n-1}+\frac{b}{a-1})$，注意这里 $a \neq 1$，而如果 $a=1$，那么 $X_n=X_{n-1}+b=X_1+(n-1)b$，可以直接用等差数列求。

因此当 $a \neq 1$ 时，$X_n+\frac{b}{a-1}=a(X_{n-1}+\frac{b}{a-1})$，又因为 $X_{n-1}+\frac{b}{a-1}=a(X_{n-2}+\frac{b}{a-1})$，因此 $X_n+\frac{b}{a-1}=a^2(X_{n-2}+\frac{b}{a-1})$，以此类推，可得 $X_n+\frac{b}{a-1}=a^{n-1}(X_1+\frac{b}{a-1})~(mod~p)$。

我们要求的是最小的 $n$ 满足 $X_n=t$，因此就是求最小的 $n$ 满足 $t+\frac{b}{a-1}=a^{n-1}(X_1+\frac{b}{a-1})~(mod~p)$，可以发现这个方程中除了 $n-1$，其他都是定值，那么我们就可以整理得到一个高次同余方程 $a^{n-1} \equiv \frac{t+\frac{b}{a-1}}{x_1+\frac{b}{a-1}}~(mod~p)$，由于 $p$ 是质数，因此等式右边的三个分数都是可以用费马定理求出关于 $p$ 的逆元，就可以将除法转换成乘法，因此等式右边就可以转化成一个整数 $b$，那么这就是一个高次同余方程的形式了。就可以用 $BSGS$ 算法来求了。

注意 $x_1+\frac{b}{a-1}$ 是有可能取到 $p$ 的倍数的，如果取到 $p$ 的倍数，那么我们可以回到上一步 $t+\frac{b}{a-1}=a^{n-1}(X_1+\frac{b}{a-1})~(mod~p)$，此时右半部分模 $p$ 就是 $0$，我们就可以将这种情况特判掉，此时 $X_n$ 恒等于 $-\frac{b}{a-1}$

另外，$a$ 和 $b$ 的范围都是 $0 \sim p-1$，因此 $a$ 和 $b$ 都可能是 $0$，我们需要将 $a$ 和 $b$ 是 $0$ 的情况也都特判掉，$a$ 还有一个 $1$ 的情况需要特判，这样剩下的 $a$ 的范围是 $2 \sim p-1$，$b$ 的范围是 $1 \sim p-1$，这个范围内的所有数就可以用 $BSGS$ 做了。可以发现本题的难点并不是 $BSGS$，而在于多个特判。

关于BSGS算法可参考

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <unordered_map>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p) //快速幂
{
    int res = 1 % p;
    while(k)
    {
        if(k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int inv(int a, int p) //计算 a 模 p 的逆元
{
    return qmi(a, p - 2, p);
}

int exgcd(int a, int b, int &x, int &y) //扩展欧几里得算法
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int bsgs(int a, int b, int p) //BSGS 算法
{
    if(1 % p == b % p) return 0; //特判 0
    int k = sqrt(p) + 1;
    unordered_map<int, int> hash;
    for(int i = 0, j = b % p; i < k; i++)
    {
        hash[j] = i;
        j = (LL)j * a % p;
    }
    int ak = 1; //记录 a^k
    for(int i = 0; i < k; i++) ak = (LL)ak * a % p;
    for(int i = 1, j = ak; i <= k; i++)
    {
        if(hash.count(j)) return (LL)k * i - hash[j]; //有解直接返回
        j = (LL)j * ak % p;
    }
    return -2; //无解
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int p, a, b, x1, t;
        scanf("%d%d%d%d%d", &p, &a, &b, &x1, &t);

        if(a == 0) //特判 a = 0，则 X[n] = b
        {
            if(x1 == t) puts("1"); //第 1 天
            else if(b == t) puts("2"); //第 2 天
            else puts("-1"); //无解
        }
        else if(a == 1) //特判 a = 1，则 X[n] = X[n - 1] + b = X[1] + (n - 1) * b;
        {
            if(b == 0) puts(t == x1 ? "1" : "-1"); //特判 b = 0，此时 X[n] = X[1]
            else //否则找最小的 n 使得 X[1] + (n - 1) * b = t (mod p)，可用扩展欧几里得算法
            {
                int x, y;
                exgcd(b, p, x, y); //(n - 1) * b + p * y = t - X[1]
                x = ((LL)x * (t - x1) % p + p) % p; //求最小正整数解
                printf("%d\n", x + 1);
            }
        }
        else
        {
            int C = (LL)b * inv(a - 1, p) % p;
            int A = (x1 + C) % p; //等式右边的分母
            if(!A) //如果 A 是 p 的倍数，则 X[n] 恒等于 - b / (a - 1)
            {
                int u = (-C + p) % p;
                puts(t == u ? "1" : "-1");
            }
            else //否则就是普通情况，用 BSGS 来求
            {
                int B = (t + C) % p; //等号右边的分母
                printf("%d\n", bsgs(a, (LL)B * inv(A, p) % p, p) + 1);
            }
        }
    }
    return 0;
}