「BZOJ3122」[SDOI2013]随机数生成器

Description

小W喜欢读书,尤其喜欢读《约翰克里斯朵夫》。最近小W准备读一本新书,这本书一共有PP页,页码范围为0P10 \cdots P-1
小W很忙,所以每天只能读一页书。为了使事情有趣一些,他打算使用NOI2012上学习的线性同余法生成一个序列,来决定每天具体读哪一页。
我们用XiX_i来表示通过这种方法生成出来的第ii个数,也即小WWii天会读哪一页。这个方法需要设置33个参数a,b,X1a,b,X_1,满足0a,b,X1p10\leq a,b,X_1\leq p-1,且a,b,X1a,b,X_1都是整数。按照下面的公式生成出来一系列的整数:Xi+1aXi+b(modp)X_{i+1} \equiv aX_i+b \pmod p其中modmod表示取余操作。
但是这种方法可能导致某两天读的页码一样。
小W要读这本书的第tt页,所以他想知道最早在哪一天能读到第t页,或者指出他永远不会读到第tt页。

Input

输入含有多组数据,第一行一个正整数TT,表示这个测试点内的数据组数。
接下来T行,每行有五个整数ppaabbX1X1tt,表示一组数据。保证X1X_1tt都是合法的页码。 注意:PP一定为质数

Output

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

Sample Input

1
2
3
7  1 1 3 3
7 2 2 2 0
7 2 2 2 1

Sample Output

1
2
3 
-1

HINT

0aP1,0bP1,2P1090\leq a\leq P-1,0\leq b\leq P-1,2\leq P\leq 10^9

Solution

tXnan1x+bi=1n2ai(modp)t\equiv X_n\equiv a^{n-1}x+b\sum_{i=1}^{n-2}a_i \pmod{p}
tXnan1x1+ban11a1(modp)t\equiv X_n\equiv a_{n-1}x_1+b\frac{a^{n-1}-1}{a-1}\pmod{p}

an1t+ba1x1+ba1(modp)a^{n-1}\equiv \frac{t+\frac{b}{a-1}}{x_1+\frac{b}{a-1}} \pmod{p}

大力BSGS一波。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

ll p, a, b, x1, t;

ll ksm(ll x, ll y) {
ll res = 1;
for(; y; y >>= 1, x = x * x % p)
if(y & 1) res = res * x %p;
return res;
}
ll c;
ll solve() {
c %= p;
ll m = (int)sqrt(p) + 1;
map<int,int>v;
v.clear();
for(int i = 0; i < m; ++i) {
int val = (ll) c * ksm(a, i) % p;
if(v.find(val) != v.end()) continue;
v[val] = i;
}
a = ksm(a, m);
if(a == 0) return c == 0 ? 0 : -2;
for(int i = 0; i <= m; ++i) {
int val = ksm(a, i);
int j = (v.find(val) == v.end() ? -1 : v[val]);
if(j >= 0 && i * m - j >= 0) return i * m - j;
}
return -2;
}
int main() {
int T = read();
while(T--) {
p = read(), a = read(), b = read(), x1 = read(), t = read();
if(x1 == t) {
puts("1");
continue;
}
if(a == 0) {
x1 %= p;
t %= p;
if(x1 == t) puts("1");
else if(b % p == t) puts("2");
else puts("-1");
} else if(a == 1) {
if(b == 0) {
if(x1 == t) puts("1");
else puts("-1");
} else {
ll tmp = t - x1;
tmp = tmp * ksm(b, p - 2) % p;
tmp = (tmp + p) % p;
if((x1 + tmp * b) % p != t) {
puts("-1");
} else writeln(tmp + 1);
}
} else {
ll tmp = t + b * ksm(a - 1, p - 2) % p;
tmp %= p;
c = x1 + b * ksm(a - 1, p - 2) % p;
c %= p;
c = tmp * ksm(c, p - 2) % p;
writeln(solve() + 1);
}

}
return 0;
}