[日常摸鱼]bzoj3122 [Sdoi]2013 随机数生成器

又是写了一晚上才过的题…

题意：有一个数列$x_n=(ax_{n-1}+b) mod p$，给你$x_1,a,b,p,t$，求最小的$x_i=t$的$i$，可能不存在

一开始很自然的推出了式子$x_n \equiv a^{n-1}x_1+b*\frac{a^{n-1}-1}{a-1} \pmod p$

这时候如果$a=1$的话就特判一下然后用exgcd做

否则让$x_n=T$得到$a^{n-1}*(ax_1-x_1+b) \equiv (a-1)T+b \pmod p$

如果$ax_1-x_1+b$存在逆元的话就两边乘上逆元然后BSGS做，不存在逆元就无解啦

然后我判a=0的时候当t=b的时候返回了1…然后交上去一直wa还拍不出来

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long lint;

inline lint read()

{

    lint s=0,f=1;char c=getchar();

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}

    return s*f;

}

map<lint,lint>x;

inline lint gcd(lint a,lint b)

{

    return !b?a:gcd(b,a%b);

}

inline lint exgcd(lint a,lint b,lint &x,lint &y)

{

    if(b==0)

    {

        x=1;y=0;

        return a;

    }lint d=exgcd(b,a%b,x,y);

    lint tx,ty;tx=y;ty=x-a/b*y;

    x=tx;y=ty;

    return d;

}

inline lint mul_mod(lint a,lint b,lint p)

{

    lint res=a%p*b%p;res=(res%p+p)%p;return res;

}

inline lint pow_mod(lint a,lint b,lint p)

{

    lint res=1;

    for(;b;b>>=1,a=(a*a)%p)if(b&1)res=(res*a)%p;

    return res;

}

inline lint inv(lint a,lint p)

{

    return mul_mod(pow_mod(a,p-2,p),1,p);

}

inline lint BSGS(lint a,lint b,lint p)

{

    a%=p;x.clear();

    if(a==0&&b==0)return 1;

    if(a==0)return -1;

    lint m=ceil(sqrt(p)),t=1;

    x[1]=m+1;

    for(register lint i=1;i<m;i++)

    {

        t=mul_mod(t,a,p);

        if(!x[t])x[t]=i;

    }

    lint tmp=pow_mod(a,p-1-m,p),inv=1;

    for(register lint k=0;k<m;k++)

    {

        lint i=x[b*inv%p];

        if(i)

        {

            if(i==m+1)i=0;

            return k*m+i;

        }

        inv=mul_mod(inv,tmp,p);

    }

    return -1;

}

inline lint solve(lint p,lint a,lint b,lint x,lint t)

{

    if(x%p==t%p)return 1;

    if(a==0)

    {

        if(b%p==t%p)return 2;//before this is return 1; T_T

        return -1;

    }

    if(a==1)

    {

        lint k,l,c,tmp;c=((t-x)%p+p)%p;

        tmp=gcd(b,p);

        if(c%tmp)return -1;

        c/=tmp;

        exgcd(b,p,k,l);

        k=k*c%p;

        k=(k%p+p)%p;

        return k+1;

    }

    lint q=(x*a%p-x+b)%p;q=(q+p)%p;

    if(gcd(q,p)!=1)return -1;

    lint tmp=((a-1)*t+b)%p*inv(q,p);tmp=mul_mod(tmp,1,p);

    lint res=BSGS(a,tmp,p);

    if(res==-1)return -1;

    return ((res%p)+p)%p+1;

}

int main()

{

    lint t=read();

    while(t--)

    {

        lint p,a,b,x,T;

        p=read();a=read();b=read();x=read();T=read();

        printf("%lld\n",solve(p,a,b,x,T));

    }

    return 0;

}

巴特西

[日常摸鱼]bzoj3122 [Sdoi]2013 随机数生成器

最新文章

热门文章