XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#40874 #1222. zxh的龙王与龙马 Accepted 100 15566 ms 416 K C++ / 1.6 K q3540555 2020-07-20 9:49:56
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll phi[300];
ll sve[300];

inline int gphi(int x) {
    int ans = x;
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0) {
            ans -= ans / i;
            while (x % i == 0) x /= i;
        }
    if (x != 1)
        ans -= ans / x;
    return ans;
}

inline ll fpow(ll a, ll b, ll m) {
    a %= m;
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans *= a, ans %= m;
        a *= a, a %= m, b >>= 1;
    }
    return ans;
}

inline ll rpow(ll a, ll b, ll rge) {
    if (b == -1 || a > rge)
        return -1;
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
            if (ans > rge)
                return -1;
        }
        a *= a, b >>= 1;
        if (a > rge)
            return -1;
    }
    return ans;
}

ll cal(ll a, ll k, ll idx) {
    ll m = phi[idx];
    if (sve[k] != -1)
        return sve[k] % m;
    --k, ++idx;
    if (sve[k] != -1 && sve[k] < phi[idx])
        return fpow(a, sve[k], m);
    return fpow(a, cal(a, k, idx) + phi[idx], m);
}

int main() {
    ios::sync_with_stdio(false);
    ll a, k, p, t;
    cin >> t >> p;
    phi[0] = p, sve[0] = 1;
    for (int i = 1; i < 250; ++i) phi[i] = gphi(phi[i - 1]);
    for (int tt = 0; tt < t; ++tt) {
        cin >> a >> k;
        for (int i = 1; i <= k; ++i) sve[i] = rpow(a, sve[i - 1], p);
        cout << cal(a, k, 0) << "\n";
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：5 ms
内存：292 KiB

输入文件（1.in） 

1 1000000007
4 2

答案文件（1.out） 

256

用户输出 

256

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：389 ms
内存：268 KiB

输入文件（2.in） 

47866 100000000
2 2
2 3
5 2
999999998196445748 73
999999998802868976 110
330115488 43
99999999962539
<872782 bytes omitted>

答案文件（2.out） 

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 0
测试点 #3
Accepted
得分：100
用时：474 ms
内存：292 KiB

输入文件（3.in） 

50000 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>

答案文件（3.out） 

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 0
测试点 #4
Accepted
得分：100
用时：443 ms
内存：292 KiB

输入文件（4.in） 

50000 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>

答案文件（4.out） 

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 0
测试点 #5
Accepted
得分：100
用时：507 ms
内存：296 KiB

输入文件（5.in） 

50000 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>

答案文件（5.out） 

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 0
测试点 #6
Accepted
得分：100
用时：570 ms
内存：348 KiB

输入文件（6.in） 

50000 997520513
3621470113464171065 4
2968789883802124850 39
5347569594051065946 118
83432033801
<1216949 bytes omitted>

答案文件（6.out） 

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 0
测试点 #7
Accepted
得分：100
用时：415 ms
内存：312 KiB

输入文件（7.in） 

50000 606713124
6611947493215158045 135
1584982523316049611 88
3539735937842866531 81
5693787885
<1216860 bytes omitted>

答案文件（7.out） 

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 0
测试点 #8
Accepted
得分：100
用时：469 ms
内存：280 KiB

输入文件（8.in） 

50000 812829187
5855350549377260136 102
2659016030658488974 1
5775653747089853891 177
2688354254
<1216703 bytes omitted>

答案文件（8.out） 

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 0
测试点 #9
Accepted
得分：100
用时：476 ms
内存：376 KiB

输入文件（9.in） 

50000 754985447
6263211863002236685 125
675111652610342943 26
2613667217335592570 100
5066586338
<1217245 bytes omitted>

答案文件（9.out） 

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 0
测试点 #10
Accepted
得分：100
用时：397 ms
内存：356 KiB

输入文件（10.in） 

50000 16635747
5278232545597676808 141
5403410576366244639 102
3934894888751244107 140
704195440
<1216731 bytes omitted>

答案文件（10.out） 

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 0
测试点 #11
Accepted
得分：100
用时：646 ms
内存：284 KiB

输入文件（11.in） 

50000 557230819
3814831339452524218 200
2952117290611106295 200
8734010238900222831 200
90351599
<1243817 bytes omitted>

答案文件（11.out） 

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 0
测试点 #12
Accepted
得分：100
用时：650 ms
内存：280 KiB

输入文件（12.in） 

50000 134991421
1449196454412858142 200
6631158710045949166 200
7946096571291154232 200
79220277
<1243927 bytes omitted>

答案文件（12.out） 

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 0
测试点 #13
Accepted
得分：100
用时：610 ms
内存：280 KiB

输入文件（13.in） 

50000 822767423
4987779854051076455 200
4054073581635063018 200
6157760435520388646 200
21248322
<1243790 bytes omitted>

答案文件（13.out） 

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 0
测试点 #14
Accepted
得分：100
用时：665 ms
内存：352 KiB

输入文件（14.in） 

50000 537906827
1599879401295604897 200
670435680653051621 200
7246219387338823005 200
264959286
<1244023 bytes omitted>

答案文件（14.out） 

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 0
测试点 #15
Accepted
得分：100
用时：651 ms
内存：268 KiB

输入文件（15.in） 

50000 290020217
8249183357764367476 200
1321788721265094786 200
9189023512339982566 200
57457689
<1243848 bytes omitted>

答案文件（15.out） 

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 0
测试点 #16
Accepted
得分：100
用时：618 ms
内存：284 KiB

输入文件（16.in） 

50000 765769539
7128564976514120146 200
6921864222562678961 200
7397912931858641487 200
48823218
<1249917 bytes omitted>

答案文件（16.out） 

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 0
测试点 #17
Accepted
得分：100
用时：579 ms
内存：416 KiB

输入文件（17.in） 

50000 404226781
7054110013052294767 200
6739071992564586650 200
6695074167820119578 200
51554452
<1249917 bytes omitted>

答案文件（17.out） 

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 0
测试点 #18
Accepted
得分：100
用时：605 ms
内存：300 KiB

输入文件（18.in） 

50000 205918759
7864535863452495455 200
8207264801788470899 200
6509780416287162786 200
63436974
<1249917 bytes omitted>

答案文件（18.out） 

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 0
测试点 #19
Accepted
得分：100
用时：576 ms
内存：280 KiB

输入文件（19.in） 

50000 902252098
5872380820585804346 200
8204826273354710135 200
5268798882015191146 200
66682841
<1249917 bytes omitted>

答案文件（19.out） 

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 0
测试点 #20
Accepted
得分：100
用时：618 ms
内存：292 KiB

输入文件（20.in） 

50000 309553697
5215459355258763636 200
4654559545836413645 200
7115419969675922122 200
46128087
<1249917 bytes omitted>

答案文件（20.out） 

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 0
测试点 #21
Accepted
得分：100
用时：659 ms
内存：292 KiB

输入文件（21.in） 

50000 999332909
4827653067510048903 200
7268634473770671689 200
8388406726429148904 200
67676825
<1249917 bytes omitted>

答案文件（21.out） 

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 0
测试点 #22
Accepted
得分：100
用时：603 ms
内存：300 KiB

输入文件（22.in） 

50000 601339770
4780882845615524194 200
5833477797216073063 200
7082630927700822359 200
84060928
<1249917 bytes omitted>

答案文件（22.out） 

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 0
测试点 #23
Accepted
得分：100
用时：613 ms
内存：280 KiB

输入文件（23.in） 

50000 792756044
7519326630823204097 200
8161751777365120624 200
7417842253474867788 200
54734052
<1249917 bytes omitted>

答案文件（23.out） 

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 0
测试点 #24
Accepted
得分：100
用时：555 ms
内存：284 KiB

输入文件（24.in） 

50000 230464884
7380687923677511956 200
9005629836382799675 200
8506722756869466953 200
67679408
<1249917 bytes omitted>

答案文件（24.out） 

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 0
测试点 #25
Accepted
得分：100
用时：641 ms
内存：348 KiB

输入文件（25.in） 

50000 1000000007
8367155240355456877 200
6147015349797667241 200
8468733805855399991 200
7369213
<1249918 bytes omitted>

答案文件（25.out） 

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 0
测试点 #26
Accepted
得分：100
用时：467 ms
内存：344 KiB

输入文件（26.in） 

50000 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>

答案文件（26.out） 

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 0
测试点 #27
Accepted
得分：100
用时：396 ms
内存：288 KiB

输入文件（27.in） 

50000 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>

答案文件（27.out） 

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 0
测试点 #28
Accepted
得分：100
用时：448 ms
内存：348 KiB

输入文件（28.in） 

50000 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>

答案文件（28.out） 

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 0
测试点 #29
Accepted
得分：100
用时：431 ms
内存：312 KiB

输入文件（29.in） 

50000 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>

答案文件（29.out） 

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 0
测试点 #30
Accepted
得分：100
用时：390 ms
内存：352 KiB

输入文件（30.in） 

50000 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>

答案文件（30.out） 

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
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号