「bzoj

BZOJ3122-[Sdoi2013]随机数生成器
有递推式X(i+1)=(aX(i)+b) mod p, 求最小的i使X(i)=t

题解

$$X_i=aX_{i-1}+b$$

$$ quad=a^2X_{i-2}+ab+b​$$

$$=…$$

$$ quad=a^{i-1}X_{1}+a^{i-2}b+a^{i-1}b+…+ab+b​$$

$$ quad=a^{i-1}X_{1}+b{a^{i-1}-1 over a-1}​$$

又$X_i=t$,有$$a^{i-1}X_1+b{a^{i-1}-1 over a-1}≡t mod p$$

其中只有$a_{i-1}$为未知量,对其化简得

$$a^{i-1}≡{(a-1)t+b over (a-1)x_1+b} mod p​$$

其中$i$为题目要我们求的答案。

首先特判几种情况:

①$a=0$时,原式为$X_i=b$,若$t=b$,则$i=1$;否则无解,输出-1;

②$a=1$时,若$b=0$,分式分母为0,无解,输出-1;否则原式为$X_i=X_1+(i-1)b$,对$i$化简有$i={t-x_1 over b}+1$,逆元求解即可;

③$X_1=t$时,有$a^{i-1}=1$,此时易得$i=1​$;

如果不存在上述情况,对于式子

$$a^{i-1}≡{(a-1)t+b over (a-1)x_1+b} mod p$$

两边同乘$a$,有式子$$a^i≡a{(a-1)t+b over (a-1)x_1+b} mod p$$

BSGS即可求出$i$。

代码

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

#define int long long

using namespace std;

int (int a, int n, int mod)
{
long long ans = 1, base = a % mod;
while(n)
{
if(n & 1) (ans *= base) %= mod;
(base *= base) %= mod;
n >>= 1;
}
return ans;
}

int inv(int a, int p) { return qp(a, p - 2, p); }

int BSGS(int a, int b, int p)
{
map<int, int> hash;
b %= p;
int t = (int)sqrt(p) + 1;
for(int j =0; j < t; j ++)
{
int val = 1ll * b * qp(a, j, p) % p;
hash[val] = j;
}
a = qp(a, t, p);
if(a == 0) return b == 0 ? 1 : -1;
for(int i = 1; i <= t; i ++)
{
int val = qp(a, i, p);
int j = hash.find(val) == hash.end() ? -1 : hash[val];
if(j >= 0 && i * t - j >= 0) return i * t - j;
}
return -1;
}

signed main()
{
int _, p, a, b, x, t;
scanf("%lld", &_);
while(_ --)
{
scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &x, &t);
if(x == t) { puts("1"); continue; }
if(a == 0) { printf("%dn", t == b ? 2 : -1); continue; }
else if(a == 1) {printf("%lldn", b ? ((((t - x) % p + p) % p) * inv(b, p) % p + 1) : -1); continue; }
int tmp = b * inv(a - 1, p) % p;
int y = (t + tmp) % p * inv((x + tmp) % p, p) % p * a % p;
int ans = BSGS(a, y, p);
printf("%lldn", ans);
}
return 0;
}