BZOJ 3122乱数生成器

タイトルリンク:http://61.187.179.132/JudgeOnline/problem.php?id=3122
タイトル:

構想:(1)x 1=t則n=1;
(2)a=0、b=t、n=2;そうでなければ解がない.
(3)a=1の場合:

(4)a>=2:

 

i64 p,a,b,x,t;



i64 Gcd(i64 a,i64 b)

{

    if(!b) return a;

    return Gcd(b,a%b);

}



i64 exGcd(i64 a,i64 b,i64 &x,i64 &y)

{

    if(b==0)

    {

        x=1; y=0;

        return a;

    }

    i64 temp=exGcd(b,a%b,x,y);

    i64 t=x;

    x=y;

    y=t-a/b*y;

    return temp;

}



i64 deal1()

{

    t=(t-x+p)%p;

    i64 X,Y;

    i64 k=exGcd(b,p,X,Y);

    if(t%k) return -1;

    X=X*t/k%p;

    if(X<0) X+=p;

    return X+1;

}



i64 Pow(i64 a,i64 b,i64 p)

{

    i64 ans=1;

    while(b)

    {

        if(b&1) ans=ans*a%p;

        a=a*a%p;

        b>>=1;

    }

    return ans;

}



i64 reverse(i64 a,i64 b)

{

    i64 x,y;

    exGcd(a,b,x,y);

    x=(x%b+b)%b;

    return x;

}



i64 cal(i64 a,i64 b,i64 p)

{

    i64 i;

    for(i=0;i<100;i++) if(Pow(a,i,p)==b) return i;

    map<i64,int> mp;

    i64 M=sqrt(1.0*p)+1;

    for(i=M-1;i>=0;i--) mp[Pow(a,i,p)]=i;

    i64 k=Pow(a,M,p),temp;

    for(i=0;i<=M;i++)

    {

        temp=b*reverse(Pow(k,i,p),p)%p;

        if(mp.count(temp)) return i*M+mp[temp];

    }

    return -1;

}



i64 deal2()

{

    i64 c=Pow(a-1,p-2,p);

    i64 A=(x+b*c)%p,B=(t+b*c)%p;

    if(A<0) A+=p;

    if(B<0) B+=p;

    i64 X,Y;

    i64 k=exGcd(A,p,X,Y);

    if(B%k) return -1;

    X=X*B/k%p;

    if(X<0) X+=p;

    i64 temp=cal(a,X,p);

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

    return temp+1;

}



i64 cal()

{

    if(x==t) return 1;

    if(a==0) 

    {

        if(b==t) return 2;

        return -1; 

    }

    if(a==1) return deal1();

    return deal2();

}



int main()

{

    rush()

    {

        RD(p,a,b); RD(x,t);

        PR(cal());

    }

}