[bzoj3122][BSGS]随机数生成器

Description

Input

输入含有多组数据，第一行一个正整数T，表示这个测试点内的数据组数。
接下来T行，每行有五个整数p，a，b，X1，t，表示一组数据。保证X1和t都是合法的页码。

注意：P一定为质数

Output

共T行，每行一个整数表示他最早读到第t页是哪一天。如果他永远不会读到第t页，输出-1。

Sample Input

3

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\

题解

讲个笑话
我居然连
等比数列
求和公式
都不知道
大言不惭扔一个上来

$$S_n=\frac{a_1*(1-a^n)}{1-a}$$
其中a是公比
把柿子拆开
差不多是一个
$$a^nx_1+a^{n-1}b+a^{n-2}b+...+b$$
把b提出来后面就是个等比数列..
因为不知道怎么O(1)求卡了半个小时的我你敢信
一通乱化简后大概是这样
$$a^{n+1}(x_1-\frac{b}{1-a})+\frac{b}{1-a} \equiv T$$
移项就是BSGS模板了..
然后
需要一些特判
a=0或者1的情况以及x1=0的情况..

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#define LL long long
using namespace std;
map<LL,int> q;
LL mod,a,b,x1,T;
LL pow_mod(LL a,LL b)
{LL ret=1;while(b){if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{if(a==0){x=0;y=1;return b;}else{LL tx,ty;LL d=exgcd(b%a,a,tx,ty);x=ty-(b/a)*tx;y=tx;return d;}
}
LL BSGS(int y,int z)
{if(y==0&&z==0){
   return 1;}  if(y==0&&z!=0){
   return -1;}q.clear();LL k=ceil(sqrt(mod)),tmp=1,p=pow_mod(y,mod-2);q[z]=k+1;for(int i=1;i<k;i++){tmp=(LL)tmp*p%mod;LL t=(LL)tmp*z%mod;if(q[t]==0)q[t]=i;}tmp=1;p=pow_mod(y,k);for(int i=0;i<k;i++){if(q[tmp]){if(q[tmp]==k+1)return i*k+1;else return i*k+q[tmp]+1;}tmp=(LL)tmp*p%mod;}return -1;
}
int main()
{
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);int Q;scanf("%d",&Q);while(Q--){scanf("%lld%lld%lld%lld%lld",&mod,&a,&b,&x1,&T);if(x1==0){if(b==0){if(T==0)puts("1");else puts("-1");continue;}}if(a==0){if(x1==T)puts("1");else if(b==T)puts("2");else puts("-1");continue;}if(a==1){LL A=b,B=mod,x,y,K=T-x1;LL d=exgcd(A,B,x,y);if(K%d){puts("-1");continue;}x=(x*(K/d)%(B/d)+(B/d))%(B/d);if(x-(B/d)>=0)x-=(B/d);printf("%lld\n",x+1);continue;}T%=mod;LL gg=-b;gg=gg*pow_mod(a-1,mod-2)%mod;x1=(x1-gg+mod)%mod;T=(T-gg+mod)%mod;T=T*pow_mod(x1,mod-2)%mod;printf("%lld\n",BSGS(a,T));}return 0;
}