BZOJ 3122 随机数生成器

发表于 | 更新于

Link

想到了b=0是BSGS，然后化式子，结果化错了，以为不会，就弃疗了。。

Solution

化出式子， 同乘a−1a-1，BSGS，真好哈。 然后写，写完WA。本地测90。 想不透。研究数据无果。事实证明我太naive。 这个xix_i每次都要 ，怎么能把分母带着呢？？ 于是把1a−1\dfrac 1{a-1}换成inv(a−1)inv(a-1)，重新划划式子，改上，WA。 无奈，又查了查，发现BSGS写错了。mid=Pmid=\sqrt P，应该取上整，这样imid−jimid-j才能取遍[0,P][0,P]。之前写BSGS从没出过这种问题，说明还算是比较隐蔽的。。要好好记着。

Tips

思考题还是要慢点，不要急躁。 用高中数学方法化出来的式子不一定能直接套到模型里，尤其是很可能不适用于在同余系。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
typedef long long LL;
int P;
int add(int a,int b){return ((LL)a+b)%P;}
int mul(int a,int b){return (LL)a*b%P;}
int Pow(int x,int v)
{
	int res=1;
	while(v)
	{
		if(v&1)
			res=mul(res,x);
		x=mul(x,x);
		v>>=1;
	}
	return res;
}
int inv(int x)
{
	return Pow(x,P-2);
}
int exgcd(int a,int b,LL &x,LL &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	else
	{
		int d=exgcd(b,a%b,x,y);
		LL nx=y,ny=x-(a/b)*y;
		x=nx,y=ny;
		return d;
	}
}
LL ExGCD(int a,int b,int c)//ax+by=c
{
	LL x,y;
	int d=exgcd(a,b,x,y);
	if(c%d) return -2;
	x*=c/d;int k=b/d;
	((x%=k)+=k)%=k;
	return x;
}

namespace iHash
{
	const int SIZE=1e6,P=1e5+7;
	struct Node
	{
		int val,key;Node *pre;
		Node(int val,int key,Node* pre):val(val),key(key),pre(pre){}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*head[P];
	Node *newNode(int val,int key,Node *pre){return new(ME++) Node(val,key,pre);}
	void Insert(int val,int key)
	{
		int hs=key%P;
		head[hs]=newNode(val,key,head[hs]);
	}
	int Find(int key)
	{
		int hs=key%P;
		for(Node *ptr=head[hs];ptr;ptr=ptr->pre)
			if(ptr->key==key) return ptr->val;
		return -1;
	}
	void Clear()
	{
		ME=POOL;memset(head,0,sizeof(head));
	}
}
LL BSGS(int a,int b,int P)//return -2!!
{
	if(a%P==0) return -2;
	iHash::Clear();
	int mid=(int)sqrt(P)+1;
	int aib=b;
	for(int i=0;i<=mid;i++)//val key
	{
		if(iHash::Find(aib)==-1)
			iHash::Insert(i,aib);
		aib=mul(aib,a);
	}
	int asp=Pow(a,mid),akj=asp;
	for(int i,j=1;j<=mid;j++)
	{
		if((i=iHash::Find(akj))!=-1)
			return mid*j-i;
		akj=mul(akj,asp);
	}
	return -2;
}

int main()
{
	//freopen("input","r",stdin);
	int T;get(T);int a,b,X1,t;
	while(T--)
	{
		get(P),get(a),get(b),get(X1),get(t);
		if(X1==t) puts("1");
		else if(a==0) printf("%d\n",b==t?2:-1);
		else if(a==1) printf("%lld\n",ExGCD(b,P,t-X1)+1);
		else
		{
			/*int x=X1;
			for(int i=1;i<=100;i++)
				printf("f(%d)=%d\n",i,x=add(mul(x,a),b));*/
			int binvam1=mul(b,inv(a-1)),y=add(t,binvam1),k=add(X1,binvam1);
			printf("%lld\n",BSGS(a,mul(y,inv(k)),P)+1);
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * WA Naive.
 * * * * * * * * * */