BZOJ3122 [SDOI2013] 随机数生成器

发表于 2017-11-24 分类于题解

已知 \(a,b,X_1,p,t\) ，

给定递推公式 \(X_{i+1}=(aX{i}+b)\mod p(i\ge 1)\) ，求最小的正整数i满足 \(X_i=t\) ，p为质数。 ### 题解这道题需要分类讨论：

当\(X_1=t\)时，答案为1.
当a=0时，如果b=t，则答案为2，否则无解。
当a=1时，原题化为\(X_1+ib\equiv t\),求最小正整数解，也就是\(ib\equiv t-x_1\)。

当a>1，显然 \[ \begin{split} X_i & = a^{i-1}X_1+b\times (1+a+a^2+...+a^{n-2})\\\\ & = a^{i-1}X_1+b\times \frac{a^{n-1}-1}{a-1}\\\\ & = a^{i-1}X_1+\frac{b\times a^{n-1}}{a-1}-\frac{b\times 1}{a-1}\\\\ & = a^{i-1}(X_1+\frac{b}{a-1})-\frac{b\times 1}{a-1}\equiv t(\mod p) \end{split} \] ，所以 \[(X_1+\frac{b}{a-1})a^{i-1}\equiv t+\frac{b\times 1}{a-1}(\mod p)\] \[a^{i-1}\equiv \frac{t+\frac{b\times 1}{a-1}}{X_1+\frac{b}{a-1}}(\mod p)\] \[a^{i-1}\equiv \frac{t(a-1)+b}{X_1(a-1)+b}(\mod p)\]

BSGS即可。

/*
Author: CNYALI_LK
LANG: C++
PROG: 3122.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll p,a,b,x1,t;
ll fpm(ll a,ll b){
    ll c=1;
    while(b){
        if(b&1)c=c*a%p;
        a=a*a%p;
        b>>=1;
    }
    return c;

}
ll inv(ll a){
    ll b=p-2,c=1;
    while(b){
        if(b&1)c=c*a%p;
        a=a*a%p;
        b>>=1;
    }
    return c;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll BSGS(ll a,ll b){
    if(b==1)return 1;
    ll m=ceil(sqrt(p));
    tr1::unordered_map<ll,ll> mp;
    for(ll i=1;i<=m;++i){
        b=b*a%p;
        mp.insert(make_pair(b,i));
    }
    b=1;
    a=fpm(a,m);
    for(ll i=1;i<=m;++i){
        b=b*a%p;
        if(mp.count(b))return i*m-mp[b]+1;
    }
    return -1;
}
int main(){
#ifdef cnyali_lk
    freopen("3122.in","r",stdin);
    freopen("3122.out","w",stdout);
#endif
    ll T;
    scanf("%lld",&T);
    while(T){
        --T;
        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
        if(x1==t)printf("1\n");
        else
        if(a==0){
            if(b==t)printf("2\n");
            else printf("-1\n");
        }
        else if(a==1){
            if(!b)printf("-1\n");
            else{
                t=(t-x1+p)%p;
                printf("%lld\n",1+t*inv(b)%p);
            }
        }
        else{
            b=(b+t*(a-1)%p)*inv(b+x1*(a-1)%p)%p;
            printf("%lld\n",BSGS(a,b));
        }
    }
    return 0;
}