UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207640#3751. 不公因数liujinchen1006264ms20752kbC++11399b2024-07-29 18:51:482024-07-29 20:28:23

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
short num[N+5];
void init()
{
	for(int i=1;i<=N;i++)
		num[i]=2;
	num[1]=1;
	int mn=N/2;
	for(int i=2;i<=mn;i++)
	{		
		for(int k=i<<1;k<=N;k+=i)
			num[k]++;
	}
}
int main(){
	init();
	int T;
	cin>>T;	
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		printf("%d\n",num[n]-num[__gcd(m,n)]);
	}
	return 0;
}
Source code, Language: C++11

Details

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

Test #1:

score: 10
Accepted
time: 593ms
memory: 20744kb

input:

1
9699690 765049

output:

255

result:

ok "255"

Test #2:

score: 10
Accepted
time: 583ms
memory: 20748kb

input:

1
9999991 9699690

output:

1

result:

ok "1"

Test #3:

score: 10
Accepted
time: 585ms
memory: 20748kb

input:

1000
823727 5153577
1579 410540
3841999 4838829
3735790 1883554
2713 1896387
5572344 5607612
7340261...

output:

1
0
6
12
0
20
2
2
0
6
6
1
6
15
0
0
12
1
10
8
1
2
0
30
7
0
22
31
4
1
6
6
20
44
1
2
1
0
1
0
14
10
11
3...

result:

ok 1000 tokens

Test #4:

score: 10
Accepted
time: 601ms
memory: 20744kb

input:

1000
3693528 935312
5912505 641115
1601 7162874
8376814 4188407
2612301 8047784
3389026 8472565
2281...

output:

40
12
0
2
6
2
0
0
20
15
14
0
12
6
10
23
4
0
1
0
11
12
8
12
3
0
0
6
0
3
6
1
0
0
1
1
1
23
20
22
0
24
5...

result:

ok 1000 tokens

Test #5:

score: 10
Accepted
time: 577ms
memory: 20748kb

input:

1000
9053240 5474707
914309 7962027
5737455 1782825
4026921 9314209
854923 3800546
8999967 7466175
9...

output:

92
6
16
7
1
4
34
0
12
0
12
4
1
14
6
3
15
3
22
8
14
19
8
31
0
8
12
14
20
10
55
0
4
44
1
2
6
14
10
15
...

result:

ok 1000 tokens

Test #6:

score: 10
Accepted
time: 608ms
memory: 20748kb

input:

100000
5542237 5542237
6586139 3867585
7970488 3755153
7014264 5028868
4449893 895196
6815944 484043...

output:

0
10
7
58
6
8
40
3
0
6
68
12
0
7
3
22
15
14
0
0
0
6
4
0
94
14
0
11
14
31
22
44
12
4
12
0
0
0
71
11
1...

result:

ok 100000 tokens

Test #7:

score: 10
Accepted
time: 611ms
memory: 20748kb

input:

100000
3318615 5375902
8309612 8907960
1433983 8690019
4499017 8560141
4178323 8364572
1667232 26796...

output:

22
18
2
2
2
71
1
1
7
1
24
14
2
1
0
7
0
30
31
72
34
47
1
2
3
14
23
6
15
16
2
22
0
72
1
10
46
44
0
6
0...

result:

ok 100000 tokens

Test #8:

score: 10
Accepted
time: 644ms
memory: 20752kb

input:

100000
8261889 2508887
961924 9797815
1958757 6704509
2953 6461164
9114137 9114137
3170073 2251749
1...

output:

6
10
14
0
0
4
6
6
2
11
14
18
30
0
14
1
31
3
1
0
2
0
1
28
14
1
20
6
30
0
0
0
14
12
2
6
6
31
62
24
0
7...

result:

ok 100000 tokens

Test #9:

score: 10
Accepted
time: 643ms
memory: 20752kb

input:

100000
5129298 688097
806945 2018579
365683 2105001
5136870 233641
5721340 91673
6952291 6952291
806...

output:

47
6
1
31
23
0
12
0
3
2
14
1
40
12
20
1
0
0
0
1
0
6
8
30
7
2
0
3
12
22
6
1
1
0
8
7
3
22
1
44
12
3
19...

result:

ok 100000 tokens

Test #10:

score: 10
Accepted
time: 819ms
memory: 20752kb

input:

100000
778593 6838561
9318241 8343383
2707 6545526
8307967 364373
92358 5205766
5837287 5837287
9393...

output:

3
3
0
3
20
0
55
8
1
10
0
12
11
20
46
0
18
14
11
30
3
2
14
12
1
2
8
2
0
14
56
0
0
0
1
1
1
4
15
0
0
0
...

result:

ok 100000 tokens

中文 English

Server time: 2025-03-01 17:40:21 | 开源项目