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 (ll a, ll b, ll 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) {
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) {
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;
}
|
近期评论