[BZOJ 3122][Sdoi 2013]随机数生成器 离散数学

传送门·Teleport!

题目大意

给定a, b, p, t, [latex]X_1[/latex]。
问数列 [latex] \{X_{i}\}, X_i = (a \times X_{i-1}+b) % p [/latex] 的第几项为t

附赠测试数据一组!

Input: 
10
11 1 4 0 7
7 4 8 2 4
7 5 1 5 1
7 1 2 5 6
13 1 2 3 2
17 1 2 6 5
7 6 1 7 4
5 2 7 5 4
3 1 2 2 2
23 1 1 3 4
Output:
11
-1
-1
5
7
9
-1
4
1
2

解题报告

首先推出{Xn}通项
$$ {Xn}=a^{n-1}+b(a^0+a^1+a^2+…+a^{n-1}) $$
带入t得到
$$ a^{n-1}+b(a^0+a^1+a^2+…+a^{n-1}) \equiv t \pmod p $$
化简
$$ a^{n-1}+b\frac{a^{n-1}-1}{a-1} \equiv t \pmod p $$
$$ (a-1)a^{n-1}+ba^{n-1}-b \equiv t(a-1) \pmod p $$
$$ ((a-1)+b)a^{n-1} \equiv (t(a-1)+b) \pmod p $$
$$ a^{n-1} \equiv (t(a-1)+b)((a-1)+b)^{-1} \pmod p $$
然后发现这就是个离散对数。。默写一下BSGS
最后进行特判a=0,1和b=0,1的情况,a=1时直接解线性同余方程,其他的都比较简单不说了。
最后吐槽: 扩展欧几里得求逆元时没有特判无解。。卡我一个小时%>_<%要吐血了……

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>

typedef long long LL;

void exgcd (LL a, LL b, LL & x, LL & y, LL & d) {
    if(b == 0) {
        x = 1, y = 0, d = a;
        return ;
    }
    exgcd(b, a%b, x, y, d);
    LL t = x; x = y; y = t-a/b*y;
}
//Ax = B (mod P)
const LL NOSOL = -193718391378LL;
LL linerCT(LL A, LL B, LL P) {
    LL X, Y, D;
    exgcd(A, P, X, Y, D);
    if(B % D) return NOSOL;
    B /= D; X = ((X*B%P)+P) % P;
    return X;
}
LL advPow (LL a, int b, LL c) {
    a %= c;
    LL ret = 1;
    while(b) {
        if(b & 1) ret *= a, ret %= c;
        a *= a;
        a %= c;
        b >>= 1;
    }
    return ret;
}
#include <map>
std :: map<int, int> mp;
//A^x = B (mod C)
LL BSGS (LL A, LL B, LL C) {
    A %= C;
    if(!A) {
        if(B == 0) return 1;
        else return NOSOL;
    }
    mp.clear();
    LL i = 1, r = sqrt(C)+1; mp[1] = 0;
    for(LL t = A%C; i<r; i++, (t*=A)%=C)
        if(mp.find(t) == mp.end()) mp[t] = i;
    LL D = 1, T = advPow(A, C-1-r, C);
    for(int i = 0; i<r; i++) {
        if(mp.find(D*B%C) != mp.end())
            return mp[D*B%C] + i*r;
        D = D*T%C;
    }
    return NOSOL;
}


#include <iostream>
int main () {
    int cas;
    scanf("%d", &cas);
    while(cas --) {
        LL P, a, b, X, t;
        std :: cin >> P >> a >> b >> X >> t;
        if(X == t) puts("1");
        else if(a == 0) {
            if(b == t) puts("2");
            else puts("-1");
        } else if(a == 1) {
            LL C=(t-X+P)%P,x,y;
            LL t; exgcd(b,P,x,y,t);
            if(C%t){puts("-1"); continue ;}
            C/=t;x=x*C%P;
            if(x<0)x+=P;
            std :: cout << x+1 << '\n';
        } else {
            LL r = linerCT((X*((a-1+P)%P) + b)%P, 1, P);
            if(r == NOSOL) {puts("-1"); continue ;}
            LL right = (t*(a-1+P)%P + b)%P*r% P;
            LL ans = BSGS(a, right, P);
            if(ans == NOSOL) ans = -2;
            std :: cout << ans+1 << '\n';
        }
    }
}