BSGS 模版题

$$\begin{aligned}ax_i+bz&\equiv x_{i+1} \pmod p\\a(x_i+\lambda) &\equiv (x_{i+1}+\lambda) \pmod p\\\lambda a-\lambda &\equiv b \pmod p\\\lambda& \equiv \frac b {a-1} \pmod p\\f_i &= x_i + \lambda\\f_x &\equiv a^{x-1}f_1\pmod p\end{aligned}$$

直接 bsgs 即可。

注意几个特判，

• $a=1,b=0$ 时，显然只有 $x_i = t$ 的时候有解 $1$。
• $a = 0$ 时，答案是 $0,1,2$ ，判断一下 $x_1,t,b$ 的关系即可。
• $a = 1,b\neq 0$ 时，原来那么做是不行的，直接化一下变成 $x_i = x_1+b(i-1)$ ，输出 $\frac{x_i-x_1}{b}+1$ 即可。
• 然后注意一下 $\frac{f_x}{f_1} = 0$ 的情况就好啦。

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int P;
int n , m;

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = 1ll * ret * x % P;
        x = 1ll * x * x % P , a >>= 1;
    }
    return ret;
}

int p , a , b , x1 , t;
map<int,int> M;
void solve() {
    M.clear();
    scanf("%d%d%d%d%d",&P,&a,&b,&x1,&t);
//    cout << Pow( 47 , 12 ) << endl;
    if( b == 0 && a == 1 ) return printf("%d\n",x1 == t ? 1 : -1) , void();
    if( a == 1 ) {
        t = ( t + P - x1 ) % P;
        printf("%d\n",t * 1ll * Pow( b , P - 2 ) % P + 1);
        return;
    }
    if( a == 0 ) {
        printf("%d\n",x1 == t ? 1 : t == b ? 2 : -1 );
        return;
    }
    int lam = 1ll * b * Pow( a - 1 , P - 2 ) % P;
    t = ( t + lam ) % P , x1 = ( x1 + lam ) % P;
    if( !t && !x1 ) return puts("1") , void();
    t = t * 1ll * Pow( x1 , P - 2 ) % P;
    if( t == 0 ) return puts("-1") , void();
    int r = ceil( sqrt( P ) ) , f = 1;
    M[f] = 0;
    for( int i = 1 ; i <= r ; ++ i ) {
        f = 1ll * f * a % P;
        if( !M.count( f ) ) M[f] = i;
    }
    int bh = Pow( a , ( ( P - 2 ) * 1ll * r ) % ( P - 1 ) );
    if( M.count( t ) ) return printf("%d\n",M[t] + 1) , void();
    for( int i = 1 ; i <= r ; ++ i ) {
        t = 1ll * t * bh % P;
        if( M.count( t ) ) return printf("%d\n",M[t] + 1 + i * r ) , void();
    }
    puts("-1");
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
    int T;cin >> T;while( T-- ) solve();
//    solve();
}