转：http://blog.csdn.net/nike0good/article/details/9181325?utm_source=tuicool
3122: [Sdoi2013]随机数生成器
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 258 Solved: 130
[Submit][Status]
Description
Input
输入含有多组数据，第一行一个正整数T，表示这个测试点内的数据组数。
接下来T行，每行有五个整数p，a，b，X1，t，表示一组数据。保证X1和t都是合法的页码。
Output
共T行，每行一个整数表示他最早读到第t页是哪一天。如果他永远不会读到第t页，输出-1。
Sample Input
3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1
Sample Output
1
3
-1
HINT
0<=a<=P-1,0<=b<=P-1,2<=P<=10^9
注意考虑特殊情况(a=1,a=0)不构成等比数列
具体可参考BSGS
值得一提的是我现场YY的负数逆元竟然对了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXA (1000000000)
#define MAXN (100000)
typedef long long ll;
ll p,a,b,x1,t;
ll pow2(ll a,ll b)
{
if (b==0) return 1;
if (b==1) return a%p;
ll c=pow2(a,b/2);
c=c*c%p;
if (b&1) c=c*a%p;
return c;
}
ll exgcd(ll a,ll b,ll&x,ll &y)
{
if (!b) {x=1,y=0;return a;}
ll g=exgcd(b,a%b,x,y);
ll t=x;x=y;y=t-(a/b)*y;
return g;
}
ll Modp(ll a,ll b,ll p)
{
b=(b+abs(b)/p*p+p)%p;
ll d,x,y,g=exgcd(a,p,x,y);
if (b%g) return -1;
d=b/g,x*=d,y*=d;
return x=(x+abs(x)/p*p+p)%p;
}
ll mulinv(ll x)
{
/*
ll ans=1;
if (x<0) x=-x,ans=-1;
return ans=ans*Modp(x,1,p); */
return Modp(x,1,p);
}
ll h[MAXN],hnum[MAXN];
int hash(ll x)
{
int i=x%MAXN;
while (h[i]&&hnum[i]^x) i=(i+1)%MAXN;
return i;
}
void ins(ll x,ll i)
{
int t=hash(x);
h[t]=i;hnum[t]=x;
}
ll babystep(ll a,ll b,ll p)
{
ll m=(ll)sqrt((long double)p)+1;
ll ans=-1;
ll res=b,uni=pow2(a,m);
if (!uni) if (!b) return 1;else return -1;
else
{
Rep(i,m+1) ins(res,i+1),res=res*a%p;
res=uni;
For(i,m)
{
int t=hash(res);
if (h[t]) {ans=i*m-(h[t]-1);break;}
res=res*uni%p;
}
Rep(i,MAXN) h[i]=hnum[i]=0;
return ans;
}
}
ll work()
{
if (x1==t) return 1;
if (a==0) return b==t?2:-1;
if (a==1)
{
//x+bn=t
// bn=t-x+p (mod p)
ll ans=Modp(b,t-x1+p,p);
if (ans==-1) return -1;
return ans+1;
}
ll m1=t*(1-a)-b,m2=(1-a)*x1-b;
m1=(m1+abs(m1)/p*p+p)%p;
m2=(m2+abs(m2)/p*p+p)%p;
ll m3=mulinv(m2);
if (m3<0) return -1;
m1=m1*m3%p;
ll ans=babystep(a,m1,p);
if (ans<=-1) return -1;else return ans+1;
// return 0;
}
int main()
{
// freopen("bzoj3122.in","r",stdin);
int T;cin>>T;
while (T--)
{
cin>>p>>a>>b>>x1>>t;
cout<<work()<<endl;
}
return 0;
}