题目描述

给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。

GCD(x,y)即求x，y的最大公约数。

输入格式

输入一个整数N

输出格式

输出一个整数，表示满足条件的数对数量。

数据范围

1≤N≤10^7

样例

4

方法一

欧拉函数+前缀和

简单梳理下思路：
如果两个数的gcd为质数p，那么
1, 这两个数一定是p的倍数
2, 这两个数除以p以后一定互质

问题转化为：求1到n/p中任意两个互质的数对个数
1, 它的值为：phi(1) + … + phi(n/p)
2, 遍历每个p求和即为答案

方法：
1, 欧拉筛正好可以求n以内的质数和n以内的欧拉函数

注意：
1, 由于(2,4)和(4,2)是不同的两个解，需要对每个互质的数乘以2，phi(1)除外

经过以上分析，用cpp写了一把，发现TLE，换成c的全局变量过了.
不知道有什么区别，路过的大佬帮看下，先行谢过

时间复杂度

O(N)

C++ TLE代码

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

int get_eulers(int n, vector<int>& euler, vector<int>& prime) {
    int cnt = 0;
    vector<bool> st(n+1, true);

    euler[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (st[i]) {
            prime[cnt++] = i;
            euler[i] = i-1;
        }

        for (int j = 0; prime[j] <= n/i; ++j) {
            st[i*prime[j]] = false;
            if (i % prime[j] == 0) {
                euler[i*prime[j]] = euler[i] * prime[j];
                break;
            }

            euler[i*prime[j]] = euler[i] * (prime[j] - 1);
        }
    }

    return cnt;
}

int main() {
    int n;
    cin >> n;

    vector<int> euler(n+1);
    vector<int> prime(n+1);
    int cnt = get_eulers(n, euler, prime);

    vector<LL> prev(n+1);
    prev[1] = euler[1];
    for (int i = 2; i <= n; ++i) {
        prev[i] = prev[i-1] + 2*euler[i];
    }

    LL res = 0;
    for (int i = 0; i < cnt; ++i) {
        int p = prime[i];
        res += prev[n/p];
    }

    cout << res<< endl;
    return 0;
}