2019-牛客多校-Day5

Posted on | Edited on | In | Views:

C. generator 2

题意

给出 $n, x_{0}, a, b, p \quad\left(1 \leq n \leq 10^{18}, 0 \leq x_{p}, a, b<p \leq 10^{9}+9,\text{p is a prime number}\right)$ ，$q$次询问，问在序列 $x_0,x_1,\cdots,x_{n-1}$ 中最小的 $i$ ，使得 $x_i=v$

题解

需要手写Hash，对于 GSBS 中的 $c_im-r_i$ ，因为有多组，且 $a,p$ 都不变，我们可以预处理 $\large a^{im}$ ，每组样例的时间复杂度为 $\frac p m+qm $ ，所以 $m=\sqrt{\frac p q}$ 时，总的时间复杂度最小

代码

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
ll qPow(ll a, ll b, ll c) {  //求(a^b) % c
    ll ret = 1;
    while (b) {
        if (b & 0x1) ret = ret * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return ret;
}
struct Hash {
    static const int MOD = 2e6+7;
    static const int N = 2e6;
    ll head[MOD + 10], nx[N], top;
    ll hs[N], id[N];
    void init() {
        memset(head, -1, sizeof head);
        top = 0;
    }
    void insert(ll x, ll y) {//x-key y-val
        ll k = x % MOD;
        hs[top] = x; id[top] = y; nx[top] = head[k]; head[k] = top++;
    }
    ll find(ll x) {
        ll k = x % MOD;
        for (int i = head[k]; i != -1; i = nx[i]) {
            if (hs[i] == x) {
                return id[i];
            }
        }
        return -1;
    }
}hs;
ll m,n;
ll BSGS(ll a, ll b, ll p) {  // a^x == b (mod p)
  if(b==1)return 0;
    ll ans=p-1;
    for (ll i = 0; i < m; ++i) {
        if(hs.find(b)>=0){
            ans=min(ans,hs.find(b)-i);
        }
        b = b * a % p;
    }
    if(ans==p-1||ans>=n)
  return -1;
  else return ans;
}
int main() {
    int t,x,a,b,q;
    ll p;
    ll v;
    in(t);
    
    whiel(t--){
        in(n);
        in(x,a,b);
        in(p);
        in(q);
        
        if(a==1){
            while(q--){
                in(v);
                ll an=(v-x+p)%p*qPow(b,p-2,p)%p;
                if(an<n)outln(an);
                else outln(-1);
            }
        }else if(a==0){
            while(q--){
                in(v);
                if(v==x)outln(0);
                else if(v==b&&n>1)outln(1);
                else outln(-1);
            }
        }else{
            m = ceil(sqrt(1.0*p/q));
            ll tt = qPow(a,m,p), vv= 1;
            hs.init();
        
            for ( ll i = 1; ; ++i) {
                vv = vv * tt % p;
                if(hs.find(vv)==-1)
                hs.insert(vv,i*m);
                if(i*m>=p)break;
            }
            while(q--){
                in(v);
                ll c=b*qPow(a-1,p-2,p)%p;
                v=(v+c)%p*qPow(x+c,p-2,p)%p;
                outln(BSGS(a,v,p));
            }
        }
    }
    return 0;
}