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;
}