UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207633#3751. 不公因数Anthonyyan1003986ms1188kbC++11492b2024-07-29 18:32:082024-07-29 20:04:32

answer

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

int T, n, m;
int factorCounter(int x)
{
  int cnt = 0;
  for (int i = 1; 1LL * i * i <= x; i++)
    if (x % i == 0)
    {
      cnt++;
      if (i * i != x)
        cnt++;
    }
  return cnt;
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &m);
    int d = __gcd(n, m);
    int ans = factorCounter(n) - factorCounter(d);
    printf("%d\n", ans);
  }
  return 0;
}
源文件, 语言: C++11

详细

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

Test #1:

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

input:

1
9699690 765049

output:

255

result:

ok "255"

Test #2:

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

input:

1
9999991 9699690

output:

1

result:

ok "1"

Test #3:

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

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: 8ms
memory: 1188kb

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: 8ms
memory: 1184kb

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: 754ms
memory: 1188kb

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: 764ms
memory: 1188kb

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: 910ms
memory: 1184kb

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: 769ms
memory: 1188kb

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: 765ms
memory: 1184kb

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 14:11:13 | 开源项目