QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#166892#4278. GCD vs LCMjeffqiTL 1011ms4464kbC++141.9kb2023-09-06 20:12:242023-09-06 20:12:24

Judging History

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

  • [2023-09-06 20:12:24]
  • 评测
  • 测评结果:TL
  • 用时:1011ms
  • 内存:4464kb
  • [2023-09-06 20:12:24]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ull unsigned ll
#define i128 __int128
using namespace std;

namespace qiqi {
	const int P = 1e9+7,N = 1e5;
	vll sum;
	void init(int n = N) {
		vi p,mu(n+1,P); mu[1] = 1;
		for (int i = 2; i <= n; i++) {
			if (mu[i] == P) {
				mu[i] = -1; p.eb(i);
			}
			for (auto x:p) {
				if (i*x > n) {
					break;
				}
				if (!(i%x)) {
					mu[i*x] = 0;
					break;
				}
				mu[i*x] = mu[i]*mu[x];
			}
		}
		sum.assign(n+1,0);
		for (int i = 1; i <= n; i++) {
			sum[i] = (sum[i-1]+1ll*i*i*mu[i])%P;
		}
	}
	void main() {
		int n,m,lim;
		cin >> n >> m >> lim;
		lim = min({lim,n,m});
		ll ans = 0;
		auto s = [&](ll l,ll r) {
			return (l+r)*(r-l+1)/2%P;
		};
		auto calc = [&](int n,int m) {
			ll res = 0;
			if (n > m) {
				swap(n,m);
			}
			for (int l = 1,r; l <= n; l = r+1) {
				r = min(n/(n/l),m/(m/l));
				res = (res+(sum[r]-sum[l-1])*s(1,n/l)%P*s(1,m/l))%P;
			}
			return res;
		};
		for (int l = 1,r; l <= lim; l = r+1) {
			r = min({lim,n/(n/l),m/(m/l)});
			ans = (ans+s(l,r)*calc(n/l,m/l))%P;
		}
		ans = (ans+P)%P;
		string str;
		while (ans) {
			str += ans%10+'0';
			ans /= 10;
		}
		reverse(all(str));
		cout << str << '\n';
	}
}

int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	qiqi::init();

	int T = 1;
	cin >> T;
	while (T--) {
		qiqi::main();
	}

//	cout << (double)(clock()-st)/CLOCKS_PER_SEC << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 4340kb

input:

2
2 2 1
3 4 2

output:

5
45

result:

ok 2 number(s): "5 45"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4464kb

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: 2ms
memory: 4196kb

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: 2ms
memory: 4320kb

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: 2ms
memory: 4300kb

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: 997ms
memory: 4300kb

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: 1011ms
memory: 4312kb

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: 1000ms
memory: 4372kb

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: 1006ms
memory: 4336kb

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: -100
Time Limit Exceeded

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: