2018 牛客网暑期 ACM 多样训练营（第三场）H.Diff-prime Pairs 脑洞

发表于 更新于 分类于 ， 本文字数： 2k 阅读时长 ≈ 4 分钟

传送门：https://www.nowcoder.com/acm/contest/141/H

题目描述

Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters another coprime pairs problem, he comes up with diff-prime pairs problem. diff-prime pairs problem is that given N, you need to find the number of pairs (i, j), where $ i \over gcd(i,j)$ and $j \over gcd(i, j)$ are both prime and i ,j ≤ N. gcd(i, j) is the greatest common divisor of i and j. Prime is an integer greater than 1 and has only 2 positive divisors.
Eddy tried to solve it with inclusion-exclusion method but failed. Please help Eddy to solve this problem.
Note that pair (i1, j1) and pair (i2, j2) are considered different if i1 ≠ i2 or j1 ≠ j2.

输入描述:

1
2
3
Input has only one line containing a positive integer N.

1 ≤ N ≤ 107

输出描述:

1
Output one line containing a non-negative integer indicating the number of diff-prime pairs (i,j) where i, j ≤ N

示例 1

输入

1
3

输出

1
2

示例 2

输入

1
5

输出

1
6

思路

首先用数组 primecnt 来记录从 1 到 n 之间素数的个数。

$\sum_{i=1}^nprimecnt [\lfloor {n \over i}\rfloor]*(primecnt [\lfloor {n \over i}\rfloor]-1)$ 即为答案

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e7+1;

bool notprime[MAXN];
int primecnt[MAXN];
typedef long long LL;

void init()
{
    memset(notprime, false, sizeof(notprime));
    notprime[0] = notprime[1] = true;
    for(int i=2; i<MAXN; i++)
    {
        if(!notprime[i])
        {
            if( i > MAXN/i )
            {
                continue;
            }
            for(int j=i*i; j<MAXN; j+=i)
            {
                notprime[j] = true;
            }
        }
    }

    primecnt[0] =primecnt[1] = 0;
    for(int i=2; i<MAXN; i++)
    {
        if(!notprime[i])
            primecnt[i] = primecnt[i-1]+1;
        else
            primecnt[i] = primecnt[i-1];
    }
}



int sum = 0;
int n;
int temp;
LL ans = 0;
int main()
{
    init();
//    for(int i=1; i<100; i++)
//       printf("%d:%d\n", i, primecnt[i]);
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        temp = primecnt[n/i];

        ans += (LL)(1LL*(temp-1)*temp);
    }
    printf("%lld\n", ans);
    return 0;
}

总结

注意数据类型转换！ ans += (LL)(temp * (temp-1) ); 是错误的！不能把 temp * (temp-1) 转换为 long long。应该使用 (LL) temp * (temp-1)。以后再在这上面犯错剁手！

再用 % d 输出 long long 剁手！