QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277330#4278. GCD vs LCMPetroTarnavskyi#AC ✓192ms10960kbC++202.2kb2023-12-06 17:48:262023-12-06 17:48:27

Judging History

你现在查看的是最新测评结果

  • [2023-12-06 17:48:27]
  • 评测
  • 测评结果:AC
  • 用时:192ms
  • 内存:10960kb
  • [2023-12-06 17:48:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 1e9 + 7;

int mult(int a, int b)
{
	return (LL) a * b % mod;
}
int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}



const int N = 1 << 17;
int pr[N];

int mu[N];
int inv[N];
int g[N];


int f2(int n)
{
	return mult(mult(n, n + 1), inv[2]);
}

struct Fenwick
{
	int n;
	vector<int> v;
	
	void init(int _n)
	{
		n = _n;
		v.assign(n, 0);
	}
	
	void upd(int i, int x)
	{
		for (; i < n; i |= (i + 1))
			v[i] = add(v[i], x);
	}
	
	int query(int i)
	{
		LL ans = 0;
		for (; i >= 0; i = (i & (i + 1)) - 1)
			ans = add(ans, v[i]);
		return ans;
	}
}F;


VI idxQ[N];
int nQ[N], mQ[N], maxA[N];

int ans[N];
void solve(int i)
{
	
	int n = nQ[i];
	int m = mQ[i];
	
	int a = 1;
	while(a <= n && a <= m)
	{
		int rA = min(n / (n / a), m / (m / a));
		
		int cur = mult(f2(n / a), f2(m / a));
		cur = mult(cur, sub(F.query(rA), F.query(a - 1)));
		ans[i] = add(ans[i], cur);
		
		a = rA + 1;
	}
}


void init()
{
	inv[1] = 1;
	FOR(i, 2, N)
		inv[i] = mult(mod - mod / i,  inv[mod % i]);		
	
	mu[1] = 1;
	FOR(p, 2, N)
	{
		if(pr[p] != 0)
		{
			if((p / pr[p]) % pr[p] == 0)
				mu[p] = 0;
			else
				mu[p] = sub(0, mu[p / pr[p]]);
			continue;
		}
			
		mu[p] = mod - 1;
		for(int j = 2 * p; j < N; j += p)
			pr[j] = p;
	}
	F.init(N);
	FOR(d, 1, N)
	{
		for(int a = d; a < N; a += d)
		{
			int coef = mult(mu[a / d], inv[d]);
			coef = mult(coef, mult(a, a));
			F.upd(a, coef);
		}
		
		for(int i : idxQ[d])
			solve(i);
	}
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int q;
	cin >> q;
	FOR(i, 0, q)
	{
		cin >> nQ[i] >> mQ[i] >> maxA[i];
		
		idxQ[maxA[i]].PB(i);
	}

	
	init();
	
		
	FOR(i, 0, q)
		cout << ans[i] << "\n";

	return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 30ms
memory: 10300kb

input:

2
2 2 1
3 4 2

output:

5
45

result:

ok 2 number(s): "5 45"

Test #2:

score: 0
Accepted
time: 27ms
memory: 10036kb

input:

5
2 8 4
10 2 9
7 8 3
2 5 10
5 2 4

output:

88
135
742
39
39

result:

ok 5 number(s): "88 135 742 39 39"

Test #3:

score: 0
Accepted
time: 31ms
memory: 9308kb

input:

5
17 8 8
27 17 10
38 46 2
37 42 1
46 13 1

output:

4164
43084
548829
385452
61783

result:

ok 5 number(s): "4164 43084 548829 385452 61783"

Test #4:

score: 0
Accepted
time: 31ms
memory: 9164kb

input:

10
73 49 10
9 84 15
22 19 17
83 54 6
30 23 9
97 2 4
28 73 9
26 40 11
97 48 7
49 45 18

output:

2437081
119216
35475
3776013
94357
11907
794038
207296
4053849
928605

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 27ms
memory: 10304kb

input:

100
75 26 130
70 18 15
109 93 55
69 196 40
180 90 153
188 82 45
167 130 110
77 68 32
56 157 79
156 174 97
190 42 82
69 107 57
152 57 183
107 156 18
73 177 90
122 5 160
108 192 147
173 157 28
39 25 45
117 191 73
8 2 166
66 18 51
76 12 78
90 181 172
40 24 84
23 158 37
7 124 134
170 171 111
62 200 198
...

output:

733546
306373
19237886
34028538
48568920
44112548
87408560
5156750
14409270
135732487
11858723
10249690
14001574
51643353
31220267
88419
79432066
136817339
186804
92568248
88
273073
164650
49310115
177044
2583670
166176
156075703
28836450
163355481
12190226
2976316
3587981
199736999
20671629
5515762...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 182ms
memory: 9552kb

input:

10000
60891 25901 72
66133 58189 144
80100 76127 113
56312 7713 20
15505 43545 83
4224 92681 67
86783 58363 95
40265 24699 18
87356 47123 54
30695 14987 197
52463 10356 157
84648 26368 16
50778 80419 99
46382 49146 34
50613 56280 189
86933 38991 186
80758 7552 90
71787 67827 168
83791 19979 96
46722...

output:

284404918
96373873
535309348
461099945
841784545
945896104
888085842
689771956
965067892
380894217
358614755
358227820
302636397
437183183
688167153
708392634
837825190
681892339
565018759
934815238
132018214
865909091
917213245
775918553
6606175
405050042
926043331
295455464
401026368
887206079
868...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 184ms
memory: 9912kb

input:

10000
62554 65192 93
20321 87063 2
2093 4936 70
73732 93855 8
25370 7859 153
69160 30589 164
23640 16956 158
78581 15650 18
16436 61874 132
59710 54885 111
10689 24943 80
2572 45498 73
26236 8728 23
54352 83094 15
25078 88912 165
15442 51929 143
32537 86311 65
98897 42573 172
18048 16022 143
60384 9...

output:

420050295
418556129
534423440
135581584
604242189
982222273
907766122
1335731
964323129
745564918
719969084
984136419
967560692
292031211
320194285
76068359
501653123
97710554
751813948
676151477
251713114
47390196
481050873
356617118
308012788
919341272
205413120
411948557
147500771
84856142
561800...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 187ms
memory: 9568kb

input:

10000
99609 21102 48
17745 50655 73
97463 4481 184
47017 51690 50
9106 27370 56
20030 30274 67
77726 21931 25
80810 22419 86
47838 75032 10
98013 78939 11
7573 45205 174
75946 53367 121
11857 17926 173
47374 36826 56
92828 51305 118
41803 81385 71
79614 42336 53
42451 48959 182
26116 3137 73
51953 9...

output:

803253345
717183560
639413155
187503578
121473921
586802464
454386891
616688100
709541647
238988731
953335712
4692202
711163272
646023743
596118997
829900243
899985497
891060791
703919492
490519300
265275489
306785774
430053239
510576682
104549076
649200862
988737315
926167798
406987189
169293960
29...

result:

ok 10000 numbers

Test #9:

score: 0
Accepted
time: 187ms
memory: 9972kb

input:

10000
50967 61216 179
8320 40906 170
28583 47797 179
8774 10408 128
66600 33057 49
43548 74339 68
44595 74016 89
1591 133 186
62398 33841 181
70068 66592 168
34848 66416 199
58879 29586 25
57195 50083 25
152 9605 41
78591 71994 106
68540 33426 110
6424 65830 99
29883 58699 48
6321 15356 129
30906 24...

output:

589985908
321602870
650020700
679301747
746954386
304603588
54145660
253328320
278434173
822610188
155409123
519322185
654069369
404476507
595451880
498709335
457069688
888792675
843902908
814075276
55235133
410794270
440669397
865798917
359828519
439718346
835741184
689358495
664698217
365329741
70...

result:

ok 10000 numbers

Test #10:

score: 0
Accepted
time: 186ms
memory: 9716kb

input:

10000
91216 83368 28749
94001 58851 64303
37619 4900 31025
35657 97761 10834
28260 53969 25076
78794 48495 64955
11095 89965 24221
28248 56875 67608
1940 76498 17082
44095 37458 48076
42162 12644 94355
33625 43686 19244
75398 95519 33974
46398 47039 54811
70451 27574 65927
79887 16575 70606
19668 37...

output:

226485480
698885130
655539373
415110136
10830620
238298189
470702832
431926284
876997907
181725447
884993757
522464207
333008964
660831724
917154617
806582692
163638566
746408334
676354613
782162073
831808422
412937738
103997639
17286342
347256466
843005848
566678459
21025138
507635688
359304227
501...

result:

ok 10000 numbers

Test #11:

score: 0
Accepted
time: 189ms
memory: 10176kb

input:

10000
63741 54455 20960
78136 67946 68199
29661 68639 45252
33284 20971 5705
99763 38719 53069
38886 9624 57882
83973 35595 16859
28127 7665 47816
90155 12743 16605
33057 53968 49537
94376 85924 47049
57226 61077 43955
25727 7419 68219
4802 59794 91850
11861 34516 72441
77103 76329 31538
41874 19994...

output:

640053083
823122615
298809759
428777277
808601710
301440899
53983633
777616530
446215328
491831849
286297914
501956847
276163786
302996714
708787729
383093933
30031062
105683079
283655277
944955432
749113787
406271612
429086167
347130514
42619222
23303262
784516305
342692980
406056594
994475633
6338...

result:

ok 10000 numbers

Test #12:

score: 0
Accepted
time: 188ms
memory: 9820kb

input:

10000
8083 89333 87934
77850 98220 13040
70694 10627 23588
44811 63070 55509
78898 50221 37321
67610 96278 2652
34270 69611 13217
5559 17764 62937
59802 38365 35484
96444 18773 41453
44540 76832 59858
10865 44489 99122
48577 71777 63234
25034 21034 4113
48715 42583 3974
15581 2759 67536
27928 92344 ...

output:

627828359
291606758
995141939
624035496
701835781
949416003
150705575
272764766
398731131
209736497
841843690
679992185
913554983
65884676
149681574
866632463
183077893
408185677
446653502
26261503
437092468
253456683
675701831
199559197
803119371
500478997
847584140
628882901
268595187
338126418
75...

result:

ok 10000 numbers

Test #13:

score: 0
Accepted
time: 185ms
memory: 9712kb

input:

10000
88261 15830 57153
37566 13889 86535
56120 6067 10950
57617 75698 54048
93588 78028 46776
87269 58455 61367
74394 97950 92168
45199 73592 84843
80753 94257 10550
88551 80547 37877
47758 76260 8767
26598 1637 54968
41821 75400 32774
14523 24930 54342
79449 32534 64111
20693 28265 82298
76703 655...

output:

466338605
646618852
808459641
816988201
2019388
977112592
54267143
836881403
249406522
588238795
381540181
431572148
54344749
798700856
740609112
855100850
844354996
530617474
732017565
45472297
874155510
645976582
129217534
587133558
120958287
846537082
917665373
850788112
82105823
75558438
6256818...

result:

ok 10000 numbers

Test #14:

score: 0
Accepted
time: 183ms
memory: 9172kb

input:

10000
15107 83746 51021
95801 7210 33164
66917 18723 5726
6967 64492 45841
56989 12598 38107
3516 78368 89964
43637 98481 66255
5002 96454 45866
17521 2420 77214
46923 2298 62675
73920 58923 42404
77194 62273 7732
77704 54371 43640
35898 84522 56110
39854 64000 13782
48876 38935 67268
99737 54529 42...

output:

438187323
74291226
533927029
571559657
371913397
65997078
860775941
607717475
775206626
638156225
7115248
594340981
311820796
484680358
369453310
459354297
384306977
481747600
825375592
12001724
326891237
617174474
640311692
686663180
223614782
664721070
263892802
747685513
921288392
699312252
38953...

result:

ok 10000 numbers

Test #15:

score: 0
Accepted
time: 188ms
memory: 9424kb

input:

10000
44886 27494 66305
88749 25253 19774
85815 82661 89823
67711 54042 49784
45086 42357 9496
36875 3080 78300
61105 55168 9116
39291 52497 51196
30125 14601 94644
41642 29581 4003
98986 14456 91858
63421 56799 11172
78889 72286 85222
65972 86990 33541
83761 24701 54476
45561 89095 33998
33266 6589...

output:

345759969
729826510
390369896
960154943
108924844
466934904
383850705
923322789
541864650
751554454
736839671
300657328
682182539
930567053
745913344
941393099
855707545
226293240
719115003
543439197
708050526
747361008
603442004
417985277
59371327
25090416
306594050
514886739
443718114
316677787
62...

result:

ok 10000 numbers

Test #16:

score: 0
Accepted
time: 183ms
memory: 10440kb

input:

10000
15605 49520 19751
74542 99816 35180
26262 91012 76181
95988 68619 60914
32737 91544 23191
3880 27849 87221
16758 685 813
75814 25925 35276
57223 27345 94272
96297 61046 17276
86248 25378 58552
72561 95024 98581
13034 67416 96438
50877 3972 89939
22973 34831 16036
80449 72130 62840
45908 48619 ...

output:

966781810
137148289
532866877
526290785
153781005
258565243
727561971
796911004
65294749
638022809
246566632
141671239
23566100
200655259
5879388
4170129
514077349
413230390
750692078
393914343
738907990
690920789
141147248
189772804
866355306
7204936
107666892
226855511
902950077
22113192
103269298...

result:

ok 10000 numbers

Test #17:

score: 0
Accepted
time: 184ms
memory: 10796kb

input:

10000
38217 51342 19979
16554 75950 66616
89453 25444 50669
40926 88569 26501
98288 48573 46481
42672 11319 42601
49611 78206 93204
57850 80849 25717
31316 25186 35111
30898 85618 78661
65328 89552 8941
69630 90908 60376
59389 35155 53197
23412 72496 39597
89502 29207 64894
93594 43090 74160
52005 4...

output:

731087378
553177143
571802016
435391130
970695964
523921426
626822768
207440471
711537529
543380527
465397124
482018697
791420168
542142331
50509134
162925739
713903247
472486629
614481763
662454086
646505310
63178661
158160083
765225388
789299874
449564912
885195834
103482790
709052142
371389479
20...

result:

ok 10000 numbers

Test #18:

score: 0
Accepted
time: 187ms
memory: 9452kb

input:

10000
30268 46430 7728
67389 67681 8392
85892 84469 49419
71623 24799 98303
72112 11438 25621
84390 22101 75425
44117 85592 286
35005 25319 82027
43531 61111 81687
63937 85509 54342
5871 11281 34013
59807 70301 23963
7205 1727 60572
78243 5210 25105
33656 61372 76760
41326 25014 41910
7334 54782 152...

output:

877199317
440337719
94368199
890749436
697874208
996387123
884825828
199162511
617518486
607688660
665935260
315977273
247953249
184694378
542597611
367671098
309724830
143138148
386581168
895165261
11359230
704684671
935186183
142651376
747829489
448688228
87421683
582218578
488057648
270689185
500...

result:

ok 10000 numbers

Test #19:

score: 0
Accepted
time: 187ms
memory: 10168kb

input:

10000
39218 64870 62018
25138 36618 18474
10904 81637 77436
32052 17647 78570
7322 7733 47337
5096 25358 65145
68383 20427 17253
75959 3192 92077
90203 73560 26012
79670 51840 91473
96787 66334 74144
7273 37791 6040
52676 19348 40945
88688 69366 9948
31015 938 51093
42534 74411 37254
4978 49994 5679...

output:

27196517
62524478
748268630
977735135
6602189
388426173
588189444
50603297
420576805
823840733
61378522
588492183
615072991
855655770
59849193
237786373
21172261
813500564
730719688
422196915
909834859
849424068
889012806
143940266
133823086
110020177
28821528
467194718
758342688
792223578
839960109...

result:

ok 10000 numbers

Test #20:

score: 0
Accepted
time: 187ms
memory: 9584kb

input:

10000
3963 6303 56485
8735 61019 8278
83503 4795 1617
84801 53525 74826
39561 30754 66308
72482 99813 71009
81753 62294 88095
85698 91960 76433
39182 20914 41336
3611 93790 97716
50813 675 16939
80539 9645 97611
51501 64094 3768
61816 90014 84099
47020 18638 83743
55058 54682 1685
83832 99847 84455
...

output:

133659301
545822091
665778315
943804237
962042679
992033777
25478980
323497391
801670945
350098481
131747617
3307074
999385342
831289274
462595178
338113930
396310236
917412477
864322988
904534537
748418912
256984203
254482606
471184149
933779545
955355466
838665092
649463502
698593973
336969913
125...

result:

ok 10000 numbers

Test #21:

score: 0
Accepted
time: 188ms
memory: 9764kb

input:

10000
2590 91997 77884
98992 36392 27417
26764 12671 65880
81122 90408 7762
26039 98831 27354
17316 74766 28243
93065 30513 56128
70053 7143 15973
14506 77485 12434
79972 76886 36224
23148 57253 68260
14964 76441 46060
2839 70391 39872
92939 11754 63834
39112 90918 2833
37757 95122 54405
3752 15991 ...

output:

938541350
956607078
510290405
705636182
815390552
526403278
859201806
92493810
443528950
733945610
741538550
286006746
603311353
242938982
641941744
749275175
388357317
528421428
596324633
181642218
863993952
216759703
668887336
410440506
364525827
103055709
272298161
102701881
456142397
462664222
7...

result:

ok 10000 numbers

Test #22:

score: 0
Accepted
time: 192ms
memory: 10960kb

input:

10000
53820 85164 56868
62527 69010 79900
38547 29471 83692
31515 50868 76054
27859 74671 66358
66774 56440 835
91267 12539 71589
66126 40422 29109
5780 6249 85792
9134 87980 88587
37285 39072 72937
22789 51008 10726
88334 62042 23600
43679 2381 73051
54533 42614 25522
11211 60586 97307
87189 78557 ...

output:

110703376
291670804
855067950
753052388
784005847
962249572
717566809
920838705
880432477
644013935
919270463
549772407
913222672
176883240
430156687
698080426
977410316
70529441
503913231
376839971
794108021
367529989
182584190
183320147
899807409
282879724
380387472
688252914
184655352
189140564
1...

result:

ok 10000 numbers

Test #23:

score: 0
Accepted
time: 184ms
memory: 9764kb

input:

10000
91190 12454 14861
82604 39335 38196
21793 15643 55574
67366 7527 85861
36078 41264 49776
68555 78157 50010
31573 37305 51995
49339 79360 17807
63081 57839 57705
56189 28282 26667
65581 65110 36485
34813 29167 62615
12676 73935 10629
2636 8603 98518
20548 87791 21395
20865 51142 53619
37130 444...

output:

383900344
258698434
690296650
915054068
424372374
135174548
335847640
398344146
915264409
670686814
673990569
977513322
685890902
321106888
516405653
903138476
760243167
216805318
403458125
345354756
317497298
749366996
938731823
335857114
904019385
226066634
146102112
378136100
565023552
206909908
...

result:

ok 10000 numbers

Test #24:

score: 0
Accepted
time: 183ms
memory: 9708kb

input:

10000
5705 33490 11341
14108 98148 83033
91922 77701 34587
26276 33246 77422
8769 96076 91059
89923 86254 64266
43919 87755 6307
41940 65801 93329
69988 60577 96929
54717 74063 70803
20572 97129 53324
18108 78901 49492
98620 82002 9487
90676 96325 96557
25622 1322 22435
69115 14114 98319
81775 78930...

output:

15999162
144332499
73354010
177475682
341437683
927213510
915099414
775451509
420901558
240318550
549540341
117751879
347209465
195616697
458049630
533121643
756964366
850653355
174646097
167029879
966451404
284369448
596741293
305735283
169715872
625105770
716429129
999127315
63091673
905672654
669...

result:

ok 10000 numbers

Test #25:

score: 0
Accepted
time: 184ms
memory: 10464kb

input:

10000
5736 96341 13084
85624 7065 94148
61068 78174 92677
5464 2792 21698
43881 15567 28205
53839 82471 79533
28770 96652 94864
65904 89414 74381
52625 36678 73814
36938 40847 33525
36392 27811 32220
74179 33819 27054
30477 79020 66260
35791 18081 30561
64957 10344 4083
95022 10088 72470
90524 5588 ...

output:

829181249
816840224
866569619
737706898
746982577
591817599
973849413
780706390
715129896
985856045
801974064
892533103
287541855
321991460
421989993
386423995
175898139
986749918
408554602
51620745
342769661
603665351
987806562
899444034
354408620
941754747
513031506
244208336
410747233
446016216
5...

result:

ok 10000 numbers

Test #26:

score: 0
Accepted
time: 187ms
memory: 10680kb

input:

10000
72736 80740 18370
51643 64553 97311
86557 77513 26700
76092 86383 93771
55105 43854 67417
73472 72032 86812
66098 8364 93587
65633 97034 54620
80365 91006 6737
67796 69679 11934
71872 32672 767
19807 39808 45968
82595 36106 9728
58636 66497 26722
59119 25976 14822
6481 58870 62714
33054 76894 ...

output:

490658342
137804883
330767937
179360908
816499368
26124637
844082700
107749772
176381111
856101989
647046762
238441452
4170921
423554101
208197392
707274633
741551129
919185617
996693470
731780827
734855792
232515189
124834714
621529211
438837986
734911035
858441052
115203000
698546546
352325460
723...

result:

ok 10000 numbers

Test #27:

score: 0
Accepted
time: 187ms
memory: 9732kb

input:

10000
12565 3921 46855
44889 53090 73381
73429 44113 91399
4702 21196 89394
79167 23292 96630
36760 44460 76124
55990 8456 73272
32039 38585 38953
23067 35312 25322
91495 1679 77779
38992 32328 7089
20177 53213 64385
47290 91382 67808
87947 88388 93603
76796 18630 5985
29181 23227 99411
3706 88931 9...

output:

352744061
36359576
753802500
90973743
101563219
404224487
257776114
742496254
736569036
477594460
438384719
566288547
207725604
158209509
560315087
354577939
455116494
877053295
315536186
821990529
615602592
575715345
461229595
229721705
178474909
376079952
665966147
627942350
886601342
572443926
10...

result:

ok 10000 numbers

Test #28:

score: 0
Accepted
time: 126ms
memory: 10316kb

input:

10000
9920 9920 9920
39068 39068 39068
70486 70486 70486
75695 75695 75695
73746 73746 73746
17953 17953 17953
45454 45454 45454
73531 73531 73531
99085 99085 99085
89377 89377 89377
87350 87350 87350
49651 49651 49651
80428 80428 80428
15597 15597 15597
36635 36635 36635
10865 10865 10865
36709 367...

output:

121260313
454499391
794464814
512312613
971373935
197412953
308148746
90847289
23193682
708048941
526862064
915656420
546773700
606063489
520978913
950866310
327372816
298267544
284529346
217153819
507250411
360027519
732105133
903822347
254735937
886344649
207029741
815249440
382332114
551549277
59...

result:

ok 10000 numbers

Test #29:

score: 0
Accepted
time: 163ms
memory: 9784kb

input:

10000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
100000 100000 100000
...

output:

114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
114479666
...

result:

ok 10000 numbers