【BZOJ3122】随机数生成器（BSGS，数论）

题面

BZOJ

洛谷

题解

考虑一下递推式

发现一定可以写成一个

\(X_{i+1}=(X_1+c)*a^i-c\)的形式

直接暴力解一下

\(X_{i+1}+c=a(X_i+c)\)

解得\(c=\frac{b}{a-1}\)

这样子，相当于得到了一个\(k*a^x\equiv t+c(mod\ p)\)这样的式子

这个显然是个裸的\(BSGS\)

直接解出来就行了

注意特判一下\(a=0,a=1,X1=t\)这几种情况。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int fpow(int a,int b,int MOD)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

const int HashMod=111111;

struct HashTable

{

	struct Line{int u,v,next;}e[100000];

	int h[HashMod],cnt;

	void Add(int u,int v,int w){e[++cnt]=(Line){w,v,h[u]};h[u]=cnt;}

	void clear(){memset(h,0,sizeof(h));cnt=0;}

	void Insert(int x,int i){Add(x%HashMod,i,x);}

	int Query(int x)

	{

		for(RG int i=h[x%HashMod];i;i=e[i].next)

			if(e[i].u==x)return e[i].v;

		return -1;

	}

}Hash;

int BSGS(int a,int y,int z,int p)

{

	if(y%p==0)return -2;

	if(z==a)return -1;

	Hash.clear();

	int m=sqrt(p)+1;

	for(RG int i=0,t=z;i<m;++i,t=1ll*t*y%p)Hash.Insert(t,i);

	for(RG int i=1,tt=fpow(y,m,p),t=1ll*a*tt%p;i<=m;++i,t=1ll*t*tt%p)

	{

		int B=Hash.Query(t);if(B==-1)continue;

		return i*m-B;

	}

	return -2;

}

int main()

{

	int T=read(),p,a,b,c,X1,t;

	while(T--)

	{

		p=read();a=read();b=read();X1=read();t=read();

		if(X1==t){puts("1");continue;}

		if(a==0){if(b==t)puts("2");else puts("-1");continue;}

		if(a==1)

		{

			if(b==0){puts("-1");continue;}

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

			t=1ll*t*fpow(b,p-2,p)%p;

			printf("%d\n",t+1);

			continue;

		}

		c=1ll*b*fpow(a-1,p-2,p)%p;

		t=(t+c)%p;X1=(X1+c)%p;

		printf("%d\n",BSGS(X1,a,t,p)+1);

	}

	return 0;

}