[SDOI2013]随机数生成器

这道题也是一道BSGS。

 不难推出

那么只要求满足

的最小x即可，这一步可以使用BSGS解决。这道题还有一些特判，比较繁。代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}
}
int mod,y,z,blc;
int mul(int a,int b){return 1ll*a*b%mod;}
int sq(int x){return 1ll*x*x%mod;}
int mpow(int a,int b){if(b == 0)return 1;return b&1?mul(a,sq(mpow(a,b/2))):sq(mpow(a,b/2));}
int inv(int x){return mpow(x,mod-2);}
int exgcd(int a,int b,int &x,int &y){
	if(b==0){x=1;y=0;return a;}
	int d=exgcd(b,a%b,y,x);y-=1ll*a/b*x;return d;
}
unordered_map<int,int> ump;
int main() {
	int TT,a,b,x1,t;
	read(TT);
	while(TT--){
		read(mod);read(a);read(b);read(x1);read(t);
		y = a%mod;
		if(x1 == t){cout<<"1\n";continue;}
		if(a==0){
			if(b==t)cout<<"2\n";
			else cout<<"-1\n";
			continue;
		}
		if(a == 1){
			int c = (t-x1+mod)%mod,x,y;
			int d = exgcd(b,mod,x,y);
			if(c%d!=0)cout<<"-1\n";
			else{
				x=1ll*x*c/d%mod;if(x<0)x+=mod;
				cout<<x+1<<endl;
			}
			continue;
		}
		z = mul(mul(a-1,t)+b,inv(mul(a-1,x1)+b));
		ump.clear();
		blc = sqrt(mod)+1;
		int cc = 1;
		for(int i=0;i<blc;i++){
			if(!ump.count(cc))ump[cc] = i;
			cc = mul(cc,y);
		}
		int st = 1,stinv = 1,invcc = inv(cc),fnd = 0;
		for(int po = 0;po<mod;po+=blc,stinv=mul(stinv,invcc)){
			if(!fnd && ump.count(mul(stinv,z)) && mpow(y,ump[mul(stinv,z)]+po) == z){
				cout<<ump[mul(stinv,z)]+po+1<<endl;
				fnd = 1;
			}
		}
		if(!fnd) cout<<"-1\n";
	}
	return 0;
}