BZOJ 3122

传送门

先判断$x$是否等于$t$

若$a=0$,判断$b$是否等于$t$

若$a=1$,$X_n=X_1+(n-1)b\ ({\rm mod}\ p)$

设$x=n-1$,原式变为$bx+py=t-X_1\ ({\rm mod}\ p)$,直接${\rm exgcd}$解$x$

对于剩下的正常情况呢…

$$X_n=a^{n-1}X_1+b\frac{a^{n-1}-1}{a-1}\ ({\rm mod}\ p)$$

设$c$为$a-1$在${\rm mod}\ p$意义下的逆元

$$a^{n-1}(X_1+bc)=t+bc({\rm mod}\ p)$$

$$(X_1+bc)a^{n-1}+py=t+bc$$

拿${\rm exgcd}$解出$a^{n-1}$,然后再用${\rm BSGS}$算一下$n-1$

需要注意${\rm exgcd}$里面可能会出现负数

™我的hash又冲突


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
program bzoj_3122;
const mo=100007;
e=31;
var p,a,b,x1,t,n,i:longint;
h:array[0..mo,1..2]of record k,i:longint; end;
cnt:array[0..mo]of longint;
function mul(a,b:longint):longint;
begin
mul:=0;
while b>0 do
begin
if b and 1=1 then mul:=(mul+a)mod p;
a:=a<<1 mod p;
b:=b>>1;
end;
end;
function qpower(x,k:longint):longint;
begin
qpower:=1;
while k>0 do
begin
if k and 1=1 then qpower:=mul(qpower,x);
x:=mul(x,x);
k:=k>>1;
end;
end;
function exgcd(a,b:longint;var x,y:longint):longint;
var t:longint;
begin
if b=0 then
begin
x:=1;
y:=0;
exit(a);
end;
exgcd:=exgcd(b,a mod b,x,y);
t:=x;
x:=y;
y:=t-a div b*y;
end;
function solve(a,b,c:longint):longint;
var g,x,y:longint;
begin
if c<0 then c:=c mod p+p;
g:=exgcd(a,b,x,y);
if c mod g<>0 then exit(-2);
if x<0 then x:=x mod p+p;
exit(mul(x,(c div g)));
end;
function hash(x:longint):longint;
begin
hash:=1;
while x>0 do
begin
hash:=(hash*e mod mo+x mod 10)mod mo;
x:=x div 10;
end;
end;
function BSGS(x,y:longint):longint;
var m,i,j,s,inv,xx,hs:longint;
begin
m:=trunc(sqrt(p)+1-(1e-6));
s:=1;
fillchar(cnt,sizeof(cnt),0);
for i:=0 to m-1 do
begin
hs:=hash(s);
inc(cnt[hs]);
h[hs,cnt[hs]].i:=i;
h[hs,cnt[hs]].k:=s;
s:=mul(s,x);
end;
inv:=qpower(x,p-m-1);
xx:=y;
for i:=0 to m-1 do
begin
hs:=hash(xx);
for j:=1 to cnt[hs] do if h[hs,j].k=xx then exit(i*m+h[hs,j].i);
xx:=mul(xx,inv);
end;
exit(-2);
end;
function calc:longint;
var c,a_:longint;
begin
if x1=t then exit(1);
if a=0 then if b=t then exit(2) else exit(-1);
if a=1 then exit(solve(b,p,t-x1)+1);
c:=qpower(a-1,p-2);
a_:=solve((x1+mul(b,c))mod p,p,(t+mul(b,c))mod p);
exit(BSGS(a,a_)+1);
end;
begin
readln(n);
for i:=1 to n do
begin
readln(p,a,b,x1,t);
writeln(calc);
end;
end.