UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209487#3771. 除法与最大公因数qiuqiu100935ms1192kbC++11409b2024-08-04 11:45:592024-08-04 12:17:37

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize(2)
int fun(int n,int k){
	int ans=0;
	for(int i=1;i*i<=n;i++)
		if(n%i==0&&__gcd(i,n/i)==1){
			ans+=k/(n/i)*2;
			if(i*i==n) ans-=k/(n/i);
		}
	return ans;
}
signed main(){
	int T;
	scanf("%lld",&T);
	while(T--){
		int n,k;
		scanf("%lld%lld",&n,&k);
		printf("%lld\n",fun(k,n));
	}
	return 0;
}
Source code, Language: C++11

Details

小提示：点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1192kb

input:

1000
853121 1
1819694 1
2361093 1
3894483 1
4076948 1
5367770 1
6967986 1
7065846 1
8214814 1
928148...

output:

853121
1819694
2361093
3894483
4076948
5367770
6967986
7065846
8214814
9281481
10427893
11108787
125...

result:

ok 1000 tokens

Test #2:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

1000
9 1
1502141 1
2794051 1
3658745 1
4933234 1
5084572 1
6236131 1
7120221 1
8409650 1
9288749 1
1...

output:

9
1502141
2794051
3658745
4933234
5084572
6236131
7120221
8409650
9288749
10969129
11078347
12343892...

result:

ok 1000 tokens

Test #3:

score: 10
Accepted
time: 0ms
memory: 1188kb

input:

1000
74 54
76 81
22 87
79 58
89 68
10 19
95 39
38 94
55 27
67 85
91 55
64 95
98 54
80 25
84 78
15 58...

output:

6
0
0
6
12
0
18
0
4
6
18
6
8
6
24
0
0
8
4
0
0
8
12
4
46
0
6
2
12
0
4
80
24
0
22
2
4
12
2
6
32
36
0
6...

result:

ok 1000 tokens

Test #4:

score: 10
Accepted
time: 1ms
memory: 1192kb

input:

1000
85 64
34 96
49 5
29 23
35 24
85 82
23 47
4 53
79 34
1 38
37 1
10 56
39 45
41 20
20 35
46 24
12 ...

output:

2
2
18
2
10
6
0
0
12
0
37
2
8
20
4
12
2
36
0
0
34
2
0
38
28
16
0
4
30
0
0
22
34
4
4
6
14
2
2
4
12
0
...

result:

ok 1000 tokens

Test #5:

score: 10
Accepted
time: 1ms
memory: 1188kb

input:

1000
34 33
59 17
60 37
47 94
95 76
7 20
65 35
54 17
98 71
99 5
23 25
11 75
93 52
42 4
88 25
37 38
75...

output:

8
6
2
2
12
2
20
6
2
38
0
0
16
20
6
2
30
2
8
4
2
0
4
36
12
26
12
6
4
8
46
28
12
4
8
32
8
2
6
0
8
0
6
...

result:

ok 1000 tokens

Test #6:

score: 10
Accepted
time: 0ms
memory: 1192kb

input:

1000
56 72
91 41
24 96
67 9
21 38
15 33
91 57
8 8
10 85
51 28
26 26
32 100
54 17
78 16
26 15
14 85
1...

output:

12
4
0
14
2
2
10
2
0
16
6
2
6
8
12
0
6
2
10
0
24
4
24
0
2
4
10
0
34
4
38
20
74
2
2
20
0
18
0
2
0
8
2...

result:

ok 1000 tokens

Test #7:

score: 10
Accepted
time: 2ms
memory: 1192kb

input:

1000
42 9
44 76
64 89
37 62
96 82
98 22
36 21
66 19
38 96
91 69
15 82
9 88
87 45
11 26
77 95
13 47
7...

output:

8
4
0
2
6
24
12
6
2
8
0
0
20
0
8
0
20
6
0
26
10
6
0
4
2
2
0
0
2
0
6
18
4
2
8
18
4
0
2
2
2
10
2
2
6
0...

result:

ok 1000 tokens

Test #8:

score: 10
Accepted
time: 295ms
memory: 1188kb

input:

1000
671753129 9228811
374349686 820600994
359489956 816278532
507731922 75806111
106799730 54689058...

output:

144
82034
346
76536
0
97544
2516
92370
28
6216
367358
760
448
1046
3378
214848
2358
34624
32
1370
12...

result:

ok 1000 tokens

Test #9:

score: 10
Accepted
time: 329ms
memory: 1192kb

input:

1000
129054961 571376033
515503819 101300608
195342179 259173072
528018560 876546689
750216391 80157...

output:

0
1312
5118
0
274
18
18394
18
107838
1146
0
158
62076
32
3044
34940
3540972
2
2
430
59448
17986
7946...

result:

ok 1000 tokens

Test #10:

score: 10
Accepted
time: 307ms
memory: 1192kb

input:

1000
232172534 694703839
901290104 413342123
168384114 422606176
73474835 790925417
334332694 945743...

output:

0
38366
2362
0
17744
322282
3846
73848
7824
427018
25952
39378
4
3616
105504
9236
212558
0
25010
280...

result:

ok 1000 tokens

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-03-01 11:31:44 | 开源项目