Luogu P2568 GCD 题解

思路

首先我们可以根据题意列出式子： \[ \sum_{p \in {\mathbb P}}\sum_{i = 1}^{n} \sum_{j=1}^n [\gcd(i, j)=p] \] 根据一些神秘的直觉，可以将式子化简成下面的样子： \[ \sum_{p \in {\mathbb P}} \sum_{i = 1}^{\left\lfloor\frac n p\right\rfloor}\sum_{j = 1}^{\left\lfloor\frac n p\right\rfloor}[\gcd(i, j) = 1] \]

根据欧拉函数 \(\varphi\) 的定义，我们可以把式子进一步化简： \[ \begin{align*} 原式 &= \sum_{p \in {\mathbb P}} \sum_{i = 1}^{\left\lfloor\frac n p\right\rfloor} \left(2 \times \left(\sum_{j = 1}^i [\gcd(i, j)]\right)- 1\right)\\ &= \sum_{p \in {\mathbb P}} \left(2 \times\sum_{i = 1}^{\left\lfloor\frac n p\right\rfloor} \varphi(i)\right) - 1 \end{align*} \]

然后线性筛筛出所有质数和欧拉函数值，做一下前缀和就可以了。时间复杂度是 \({\mathcal O}(n)\)

代码

#include <iostream>
#include <bitset>
#include <vector>

#define int long long

using namespace std;

int n, ans, phi[10000009];
bitset<10000009> p;
vector<int> pri;

void init(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!p[i]) {
            pri.push_back(i);
            phi[i] = i - 1;
        }
        for (int j: pri) {
            if (i * j > n) {
                break;
            }
            p[i * j] = true;
            if (i % j == 0) {
                phi[i * j] = phi[i] * j;
                break;
            } else {
                phi[i * j] = phi[i] * phi[j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        phi[i] += phi[i - 1];
    }
}

signed main() {
    cin >> n;
    init(n);
    for (int i: pri) {
        ans += (phi[n / i] << 1LL) - 1;
    }
    cout << ans;
}