比赛链接

牛客2018暑假多校训练营3

H.Diff-prime Pairs

题目描述

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 \(\frac{i}{gcd(i, j)}\) and \(\frac{j}{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 \((i_1, j_1)\) and pair \((i_2, j_2)\) are considered different if \(i_1 ≠ i_2 or j_1 ≠ j_2\).

输入描述:

Input has only one line containing a positive integer \(N\).

\(1 ≤ N ≤ 10^7\)

输出描述:

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

示例1

输入

3

输出

2

示例2

输入

5

输出

6

解题思路

题目要找的即：满足这样的素数对 \((prime1,prime2)\)，且 \(max(prime1,prime2)\times d \leq n\)，不妨先把素数筛出来，再求出满足条件的 \(d\) 的个数
很容易，有个暴力代码：

long long res=0;
for(int i=1;i<=m;i++)
	for(int j=i+1;j<=m;j++)
		res+=n/prime[j];
res*=2;

会超时~
分别考虑求 \(prime[1]、prime[2]、prime[3]、\dots、prime[m]\) 的次数很容易简化代码~

• 时间复杂度：\(O(n)\)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int prime[N];
int m,n;
int v[N];
void primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
        {
            v[i]=i;
            prime[++m]=i;
        }
        for(int j=1;j<=m;j++)
        {
            if(v[i]<prime[j]||i*prime[j]>n)break;
            v[i*prime[j]]=prime[j];
        }
    }
}
int main()
{
    scanf("%lld",&n);
    primes(n);
    long long res=0;
    for(int i=1;i<=m-1;i++)
            res+=1ll*n/prime[i+1]*i;
    printf("%lld",res*2);
    return 0;
}