用户输出
256
系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #45919 | #1222. zxh的龙王与龙马 | Accepted | 100 | 9499 ms | 380 K | C++ 17 / 2.8 K | Leohh | 2020-08-08 15:14:04 |
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#define MAX_L 20005
#define pii pair<int, int>
// #define int long long
#define int __int128_t
#define ll long long
using namespace std;
int T, p, a, n, tot = 0;
int phi[MAX_L];
int getphi(int x) {
int ans = x, t = x;
for (int i = 2; i * i <= x; i++) {
if (!(t % i)) {
ans = ans / i * (i - 1);
while (!(t % i)) {
t /= i;
}
}
}
if (t != 1) {
ans = ans / t * (t - 1);
}
return ans;
}
/*
int fpow(int x, int k, int p) {
// cout << "fpow: x = " << x << " k = " << k << " p = " << p << endl;
int ans = 1;
x %= p;
while (k) {
if (k & 1) {
ans = ans * x % p;
}
x = x * x % p, k >>= 1;
}
return ans;
}
int solve(int a, int n, int p, int s) {
// cout << "solve: a = " << a << " n = " << n << " p = " << p << " s = " << s << " phi[s] = " << phi[s] <<
endl; if (p == 1) { return 0;
}
if (n == 0) {
return 1;
}
if (n == 1) {
return a % p;
}
int res = fpow(a, solve(a, n - 1, phi[s], s + 1) + phi[s], p);
// cout << "[res]: a = " << a << " n = " << n << " p = " << p << " s = " << s << " phi[s] = " << phi[s] <<
" res = " << res << endl; return res;
}*/
pii fpow(int x, int k, int p) {
// cout << "fpow: x = " << x << " k = " << k << " p = " << p << endl;
int ans = 1, xflag = 0, flag = 0;
if (x >= p) {
x %= p, xflag = 1;
}
while (k) {
if (k & 1) {
ans = ans * x;
flag |= xflag;
if (ans >= p) {
ans %= p, flag = 1;
}
}
x = x * x, k >>= 1;
if (x >= p) {
x %= p, xflag = 1;
}
}
return pii(ans, flag);
}
int solve(int a, int n, int p) {
struct Data {
int n, p, s;
};
stack<Data> st;
st.push((Data){ n, p, 1 });
while (true) {
Data t = st.top();
if (t.n <= 1 || t.p == 1) {
break;
}
st.push((Data){ t.n - 1, phi[t.s], t.s + 1 });
}
// cout << "push" << endl;
int res = 0, flag = 0;
while (!st.empty()) {
Data t = st.top();
st.pop();
// cout << "n = " << t.n << " p = " << t.p << " s = " << t.s << " phis = " << phi[t.s] << " lasres = "
// << res << " lasflag = " << flag << endl;
if (t.n == 0) {
res = 1, flag = 0;
if (res >= t.p) {
res %= t.p, flag = 1;
}
} else if (t.n == 1) {
res = a, flag = 0;
if (res >= t.p) {
res %= t.p, flag = 1;
}
} else {
pii pa;
if (flag) {
pa = fpow(a, res + phi[t.s], t.p);
} else {
pa = fpow(a, res, t.p);
}
res = pa.first, flag = pa.second;
}
}
// cout << "pop" << endl;
return res % p;
}
int read() {
ll x;
scanf("%lld", &x);
return x;
}
signed main() {
// scanf("%lld%lld", &T, &p);
T = read(), p = read();
int t = p;
while (t > 1) {
t = getphi(t);
phi[++tot] = t;
}
// cout << "getphi" << endl;
// for (int i = 1; i <= tot; i++) {
// cout << "i = " << i << " phi = " << phi[i] << endl;
// }
while (T--) {
// scanf("%lld%lld", &a, &n);
a = read(), n = read();
if (a == 1) {
printf("%lld\n", p == 1 ? 0 : 1);
continue;
}
printf("%lld\n", (ll)solve(a, n, p));
}
}
47866 100000000
2 2
2 3
5 2
999999998196445748 73
999999998802868976 110
330115488 43
99999999962539
<872782 bytes omitted>4
16
3125
39092736
5278976
86588416
67918059
0
58314496
47435776
0
0
59469393
82398976
31260416
0
34
<368526 bytes omitted>用户输出
4
16
3125
39092736
5278976
86588416
67918059
0
58314496
47435776
0
0
59469393
82398976
31260416
0
34290176
30281216
10571776
288
<368498 bytes omitted>系统信息
Exited with return code 050000 955866731
11 170
59 92
12 43
49 136
57 140
96 55
59 192
77 166
42 121
78 195
2 171
<368429 bytes omitted>244825520
207604340
72978591
321824443
488164717
106904399
207604340
585699437
662282541
595227794
3
<488781 bytes omitted>用户输出
244825520
207604340
72978591
321824443
488164717
106904399
207604340
585699437
662282541
595227794
382121032
299297100
955633822
<488753 bytes omitted>系统信息
Exited with return code 050000 416215975
30 76
66 96
32 109
36 133
4 165
44 199
29 76
40 74
1 173
43 112
54 42
74
<368201 bytes omitted>385473250
155578466
211590026
143987936
245534846
221020781
6025069
184889350
1
106374857
203047846
<481451 bytes omitted>用户输出
385473250
155578466
211590026
143987936
245534846
221020781
6025069
184889350
1
106374857
203047846
2348126
101269176
73744896
7
<481423 bytes omitted>系统信息
Exited with return code 050000 681150331
32 154
39 177
35 97
95 69
18 103
45 86
3 11
38 179
9 138
55 113
63 11
46
<368192 bytes omitted>168363573
535396347
185780965
396032772
353792923
648496057
636871298
429284473
181342247
278897645
<487993 bytes omitted>用户输出
168363573
535396347
185780965
396032772
353792923
648496057
636871298
429284473
181342247
278897645
556635879
233710997
1
603365
<487965 bytes omitted>系统信息
Exited with return code 050000 997520513
3621470113464171065 4
2968789883802124850 39
5347569594051065946 118
83432033801
<1216949 bytes omitted>221253759
895685066
758587251
384466072
210870295
986121637
815176456
352592321
885615065
412731356
<494343 bytes omitted>用户输出
221253759
895685066
758587251
384466072
210870295
986121637
815176456
352592321
885615065
412731356
246167340
968291037
87095324
<494315 bytes omitted>系统信息
Exited with return code 050000 606713124
6611947493215158045 135
1584982523316049611 88
3539735937842866531 81
5693787885
<1216860 bytes omitted>205554093
551803539
393413299
554350392
576074143
540854277
7073328
133351368
332875507
474504280
38
<490784 bytes omitted>用户输出
205554093
551803539
393413299
554350392
576074143
540854277
7073328
133351368
332875507
474504280
384342348
46906811
559632763
3
<490756 bytes omitted>系统信息
Exited with return code 050000 812829187
5855350549377260136 102
2659016030658488974 1
5775653747089853891 177
2688354254
<1216703 bytes omitted>744079185
771741090
805219748
616354100
594797381
741940649
299892539
567913507
28371221
58687916
87
<493155 bytes omitted>用户输出
744079185
771741090
805219748
616354100
594797381
741940649
299892539
567913507
28371221
58687916
87670645
663512758
210586738
5
<493127 bytes omitted>系统信息
Exited with return code 050000 754985447
6263211863002236685 125
675111652610342943 26
2613667217335592570 100
5066586338
<1217245 bytes omitted>440021632
373874281
117667433
668635687
1975382
605287756
334018402
625950258
352040664
456112881
38
<492627 bytes omitted>用户输出
440021632
373874281
117667433
668635687
1975382
605287756
334018402
625950258
352040664
456112881
389131760
15838246
8064202
584
<492599 bytes omitted>系统信息
Exited with return code 050000 16635747
5278232545597676808 141
5403410576366244639 102
3934894888751244107 140
704195440
<1216731 bytes omitted>10924416
2822565
14657717
8570820
2157397
10837879
6464842
6320000
12330149
5273194
15425309
1306938
<416289 bytes omitted>用户输出
10924416
2822565
14657717
8570820
2157397
10837879
6464842
6320000
12330149
5273194
15425309
13069384
5075538
5442872
2979687
15
<416261 bytes omitted>系统信息
Exited with return code 050000 557230819
3814831339452524218 200
2952117290611106295 200
8734010238900222831 200
90351599
<1243817 bytes omitted>299794147
156295869
277620398
498102938
465600246
319218971
176394730
189539130
170669904
50180334
9
<490009 bytes omitted>用户输出
299794147
156295869
277620398
498102938
465600246
319218971
176394730
189539130
170669904
50180334
95008116
439767885
77553413
2
<489981 bytes omitted>系统信息
Exited with return code 050000 134991421
1449196454412858142 200
6631158710045949166 200
7946096571291154232 200
79220277
<1243927 bytes omitted>101523463
22864227
25096316
99277471
35944339
132597952
124513761
132289353
111577225
91845086
19195
<458909 bytes omitted>用户输出
101523463
22864227
25096316
99277471
35944339
132597952
124513761
132289353
111577225
91845086
19195678
122377232
115212145
1096
<458881 bytes omitted>系统信息
Exited with return code 050000 822767423
4987779854051076455 200
4054073581635063018 200
6157760435520388646 200
21248322
<1243790 bytes omitted>179329987
171085143
149387505
501801808
692970503
170952244
473859759
288188832
162677618
27594944
5
<493092 bytes omitted>用户输出
179329987
171085143
149387505
501801808
692970503
170952244
473859759
288188832
162677618
27594944
510108740
773501655
812393221
<493064 bytes omitted>系统信息
Exited with return code 050000 537906827
1599879401295604897 200
670435680653051621 200
7246219387338823005 200
264959286
<1244023 bytes omitted>475521284
295510689
104471528
125775921
331980489
396430626
98737840
423243249
284606605
394072775
1
<489596 bytes omitted>用户输出
475521284
295510689
104471528
125775921
331980489
396430626
98737840
423243249
284606605
394072775
155651746
86628008
501782297
<489568 bytes omitted>系统信息
Exited with return code 050000 290020217
8249183357764367476 200
1321788721265094786 200
9189023512339982566 200
57457689
<1243848 bytes omitted>80477120
279803186
262753047
28592774
39870704
26032047
56855729
103455558
239916130
173641485
13266
<480704 bytes omitted>用户输出
80477120
279803186
262753047
28592774
39870704
26032047
56855729
103455558
239916130
173641485
132663509
161112635
200867213
151
<480676 bytes omitted>系统信息
Exited with return code 050000 765769539
7128564976514120146 200
6921864222562678961 200
7397912931858641487 200
48823218
<1249917 bytes omitted>616080358
374854334
620606181
134781526
445365712
350428258
668467830
93964458
198578257
577047069
4
<492712 bytes omitted>用户输出
616080358
374854334
620606181
134781526
445365712
350428258
668467830
93964458
198578257
577047069
497665758
379494848
579288170
<492684 bytes omitted>系统信息
Exited with return code 050000 404226781
7054110013052294767 200
6739071992564586650 200
6695074167820119578 200
51554452
<1249917 bytes omitted>241709042
222248212
57368864
195613303
70390300
72415238
388501194
152216820
78877846
337775523
1438
<486113 bytes omitted>用户输出
241709042
222248212
57368864
195613303
70390300
72415238
388501194
152216820
78877846
337775523
143844457
381375786
156676304
19
<486085 bytes omitted>系统信息
Exited with return code 050000 205918759
7864535863452495455 200
8207264801788470899 200
6509780416287162786 200
63436974
<1249917 bytes omitted>167704684
14554177
110254849
151720676
121046289
193030369
7234965
108437258
54792772
98678402
18530
<472991 bytes omitted>用户输出
167704684
14554177
110254849
151720676
121046289
193030369
7234965
108437258
54792772
98678402
18530870
77889342
101634469
44060
<472963 bytes omitted>系统信息
Exited with return code 050000 902252098
5872380820585804346 200
8204826273354710135 200
5268798882015191146 200
66682841
<1249917 bytes omitted>407500558
281144953
44858388
40981357
878612739
92542158
243535986
240198933
13171140
833929425
7747
<493753 bytes omitted>用户输出
407500558
281144953
44858388
40981357
878612739
92542158
243535986
240198933
13171140
833929425
774748496
464513714
525493026
35
<493725 bytes omitted>系统信息
Exited with return code 050000 309553697
5215459355258763636 200
4654559545836413645 200
7115419969675922122 200
46128087
<1249917 bytes omitted>141441582
308426288
83194142
11110725
241687920
244590748
202300681
50039365
72745244
231198845
7410
<481845 bytes omitted>用户输出
141441582
308426288
83194142
11110725
241687920
244590748
202300681
50039365
72745244
231198845
74101783
193687002
167697589
193
<481817 bytes omitted>系统信息
Exited with return code 050000 999332909
4827653067510048903 200
7268634473770671689 200
8388406726429148904 200
67676825
<1249917 bytes omitted>565370395
640627107
38376586
728750809
943633462
352530702
371482358
491032279
890153725
271135919
1
<494353 bytes omitted>用户输出
565370395
640627107
38376586
728750809
943633462
352530702
371482358
491032279
890153725
271135919
127572662
946091622
757895864
<494325 bytes omitted>系统信息
Exited with return code 050000 601339770
4780882845615524194 200
5833477797216073063 200
7082630927700822359 200
84060928
<1249917 bytes omitted>329680306
245655727
268678799
386268400
124765066
435821857
254776896
182269359
375212837
192923586
<490830 bytes omitted>用户输出
329680306
245655727
268678799
386268400
124765066
435821857
254776896
182269359
375212837
192923586
418852613
88001656
189203365
<490802 bytes omitted>系统信息
Exited with return code 050000 792756044
7519326630823204097 200
8161751777365120624 200
7417842253474867788 200
54734052
<1249917 bytes omitted>190425781
383960104
114110064
705164959
589682767
226628668
429602188
565227624
274479232
351027611
<492782 bytes omitted>用户输出
190425781
383960104
114110064
705164959
589682767
226628668
429602188
565227624
274479232
351027611
137766700
195616444
68469143
<492754 bytes omitted>系统信息
Exited with return code 050000 230464884
7380687923677511956 200
9005629836382799675 200
8506722756869466953 200
67679408
<1249917 bytes omitted>138802192
216645035
115794437
198012400
150190443
39076775
213444364
200039553
217518484
20876092
59
<475761 bytes omitted>用户输出
138802192
216645035
115794437
198012400
150190443
39076775
213444364
200039553
217518484
20876092
59700520
192022468
35329747
13
<475733 bytes omitted>系统信息
Exited with return code 050000 1000000007
8367155240355456877 200
6147015349797667241 200
8468733805855399991 200
7369213
<1249918 bytes omitted>77628541
878515601
309627679
672158497
949384448
267932806
420348625
653352560
774609117
729474359
4
<494323 bytes omitted>用户输出
77628541
878515601
309627679
672158497
949384448
267932806
420348625
653352560
774609117
729474359
430766681
438368019
162007701
<494295 bytes omitted>系统信息
Exited with return code 050000 536870912
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2
<401717 bytes omitted>2
4
16
65536
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<345902 bytes omitted>用户输出
2
4
16
65536
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<295874 bytes omitted>系统信息
Exited with return code 050000 387420489
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2
<401717 bytes omitted>2
4
16
65536
372572332
50977303
49488199
76947442
133229887
116630557
359282581
80571301
<404530 bytes omitted>用户输出
2
4
16
65536
372572332
50977303
49488199
76947442
133229887
116630557
359282581
80571301
139738399
35575963
142395604
137612635
<354502 bytes omitted>系统信息
Exited with return code 050000 268435456
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2
<401717 bytes omitted>2
4
16
65536
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<339228 bytes omitted>用户输出
2
4
16
65536
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<289200 bytes omitted>系统信息
Exited with return code 050000 244140625
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2
<401717 bytes omitted>2
4
16
65536
201578611
113209986
197920611
48839361
130526861
43495611
212245611
34511236
<451149 bytes omitted>用户输出
2
4
16
65536
201578611
113209986
197920611
48839361
130526861
43495611
212245611
34511236
112636236
161464361
161464361
16146436
<401121 bytes omitted>系统信息
Exited with return code 050000 362797056
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2
<401717 bytes omitted>2
4
16
65536
88428544
251330560
315031552
294129664
289650688
262776832
101533696
2224660
<469812 bytes omitted>用户输出
2
4
16
65536
88428544
251330560
315031552
294129664
289650688
262776832
101533696
222466048
222466048
222466048
222466048
222466
<419784 bytes omitted>系统信息
Exited with return code 0