BZOJ-3122: [Sdoi2013]随机数生成器

Description

0<=a<=P-1,0<=b<=P-1,2<=P<=10^9

GXZlegend讲了一个很好的做法。his blog：http://www.cnblogs.com/GXZlegend/p/7763526.html
简单点说就是发现本来的BSGS的方程是，之后通过枚举k找b是否存在的方法使得复杂度为O()。前提是a,p互质（目的：使得幂次高了之后不会出现0）
我们发现一次函数的多次复合同样满足这个性质，那就可以啦！（注意特判a=0的时候）

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
ll p,a,b,x1,t,ans,sq;
int tot;
struct node
{
    ll w,tim;
}z[101000];
bool cmp(node x,node y){return x.w==y.w?x.tim>y.tim:x.w<y.w;}
inline ll getid(ll x)
{
    int l=1,r=sq+1,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(z[mid].w>=x) r=mid;
        else l=mid+1;
    }
    if(r>sq||z[r].w!=x) return -1;
    return z[r].tim;
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
        if(!a)
        {
            if(x1==t) puts("1");
            else if(t==b) puts("2");
            else puts("-1");
            continue;
        }
        if(x1==t){puts("1"); continue;}
        ll A=1,B=0,tmp; sq=(ll)sqrt(p)+1;
        for(ll i=0;i<sq;++i)
        {
            z[i+1].tim=i;
            z[i+1].w=(A*t+B)%p;
            A=a*A%p; B=(a*B+b)%p;
        }
        sort(z+1,z+sq+1,cmp);
        a=1,b=0; ans=inf;
        for(ll i=1;i*sq<=p+sq;++i)
        {
            a=a*A%p; b=(A*b+B)%p;
            tmp=getid((x1*a+b)%p);
            if(tmp!=-1) ans=min(ans,i*sq-tmp+1);
        }
        if(ans>p) puts("-1");
        else printf("%lld\n",ans);
    }
    return 0;
}