BZOJ

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.