Luogu

BZOJ

分析

已知 $X_{i+1}\equiv aX_i+b\pmod p$ 。

两边加上 $\frac{b}{a}$ 后再乘上 $a$ ，变为
$$
aX_{i+1}+b\equiv a^2X_i+ab+b\pmod p
$$
那么就有
$$
X_{i+2}\equiv a^2X_i+ab+b\pmod p
$$
以此类推，可以得到
$$
X_{i}\equiv a^{i-1}X_1+b\sum\limits_{j=0}^{i-2}a^j\pmod p
$$
后面是个等比数列，套用等比数列求和化为
$$
X_i\equiv a^{i-1}X_1+b\frac{1-a^{i-1}}{1-a}\pmod p
$$
把 $a^{i-1}$ 提出来得到
$$
X_i\equiv a^{i-1}(X_1-\frac{b}{1-a})+\frac{b}{1-a}\pmod p
$$
进一步得到
$$
a^{i-1}\equiv \frac{X_i-\frac{b}{1-a}}{X_1-\frac{b}{1-a}}\pmod p​
$$
$a$、$b$、$X_1$、$X_i$（就是题目中的 $t$） 全部已知，BSGS 解出 $i$ 即可。

然后还有一些特判：

• $X_1=t$，答案为 $1$ 。
• $a=0$，此时对于任意的 $i$ ，都有 $X_i=b$ 。所以检查 $X_1$ 和 $t$ 是否相等即可。
• $a=1$，此时有 $t\equiv X_1+b(i-1)\pmod p$ ，直接解出 $i$ 即可。

代码

//It is made by M_sea
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int mod,a,b,x1,t;

inline int qpow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) ans=1ll*ans*a%mod;
    return ans;
}

inline int bsgs(int a,int b) {
    unordered_map<int,int> h; h.clear();
    b%=mod; int t=sqrt(mod)+1;
    for (re int i=0,j=1;i<t;++i,j=1ll*j*a%mod) h[1ll*b*j%mod]=i;
    a=qpow(a,t); if (!a) return !b?1:-1;
    for (re int i=0,j=1;i<t;++i,j=1ll*j*a%mod) {
        int k=h.find(j)==h.end()?-1:h[j];
        if (k>=0&&i*t-k>=0) return i*t-k;
    }
    return -1;
}

int main() {
    int T=read();
    while (T--) {
        mod=read(),a=read(),b=read(),x1=read(),t=read();
        if (x1==t) puts("1");
        else if (!a) {
            if (b==t) puts("2");
            else puts("-1");
        }
        else if (a==1) {
            if (!b) puts("-1");
            else printf("%d\n",1ll*(t-x1+mod)%mod*qpow(b,mod-2)%mod+1);
        }
        else {
            int tmp=1ll*b*qpow((1-a+mod)%mod,mod-2)%mod;
            int c=(t-tmp+mod)%mod,d=(x1-tmp+mod)%mod;
            int ans=bsgs(a,1ll*c*qpow(d,mod-2)%mod);
            if (ans==-1) puts("-1");
            else printf("%d\n",ans+1);
        }
    }
    return 0;
}