牛客多校 2018 第三场 H Diff-prime Pairs（素数）

Diff-prime Pairs

• 时间限制：C/C++ 1秒，其他语言2秒
• 空间限制：C/C++ 262144K，其他语言524288K
• 64bit IO Format: %lld

题目描述

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 (i1, j1) and pair (i2, j2) are considered different if i1 ≠ i2 or j1 ≠ j2.

输入描述:

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

输入

3

输出

2

输入

5

输出

6

---

链接

https://www.nowcoder.com/acm/contest/141/H

题意

问满足 $\frac{i}{gcd(i, j)}$ 和 $\frac{j}{gcd(i, j)}$都是质数的数对(i,j)的数量（$1<=i, j <= n$），(i, j)和(j, i)是不同的。

题解

$\frac{i}{gcd(i, j)} / \frac{j}{gcd(i, j)} = \frac{i}{j}$，当$\frac{x}{y} = \frac{i}{j}$时，$\frac{x}{y}*t$也符合条件，$1<=t<=n/max(x, y)$。

先筛出1到n之间所有的素数，然后从第二个素数(Prime[1])开始，找与它匹配的素数的数量(i)，答案为$ans = ans + i*n/Prime[i]$。

代码

• 代码长度：721 运行时间： 125 ms 占用内存：12896K  运行结果：答案正确

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 10;
bool isComp[maxn] = {false};
int P[maxn] = {0};
int Pcnt = 0;

void sizve(int n) // 筛法得到n以内的质数
{
    for (int i = 2; i <= n; ++i)
    {
        if (!isComp[i])
            P[Pcnt++] = i;
        for (int j = 0; j < Pcnt && i * P[j] <= n; ++j)
        {
            isComp[i * P[j]] = true;
            if (i % P[j] == 0)
                break;
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    sizve(n);
    ll ans = 0;
    for (int i = 1; i < Pcnt; ++i) // 从第二个质数3开始配对
        ans += n / P[i] * i;
    ans *= 2;
    printf("%lld\n", ans);
    return 0;
}

复习素数筛法。

---

The end.
2018-08-07 星期二