gcd(x, y) = 素数p => x / p 和 y / p互质 => x ,y是 n / p内的互质的数对 => 想到欧拉函数
素数筛预处理欧拉函数和素数
对欧拉函数求前缀和
枚举质数p,其贡献为n / p内的互质对 * 2 - 1( - 1是因为1的互质数是1,对应数对为(p, p)要减去一个)
时间复杂度: O(n)空间复杂度:O(n)
#include <bits/stdc++.h>
using i64 = long long;
const int N = 1e7;
int primes[N], cnt, n;
i64 phi[N];
std::bitset<N> isprime;
void init() {
isprime[0] = isprime[1] = 1;
phi[1] = 1;
for (int i = 2; i <= n; i ++ ) {
if (!isprime[i])
primes[cnt ++] = i, phi[i] = i - 1;
for (int j = 0; primes[j] <= n / i; j ++ ) {
isprime[primes[j] * i] = 1;
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
if (i % primes[j] == 0) {
phi[i * primes[j]] += phi[i];
break;
}
}
}
}
int main () {
std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
std::cin >> n;
init();
i64 res = 0;
for (int i = 1; i <= n; i ++ ) phi[i] += phi[i - 1];
for (int i = 0; i < cnt; i ++) {
res += (2LL * phi[n / primes[i]] - 1);
}
std::cout << res;
return 0;
}
因篇幅问题不能全部显示,请点此查看更多更全内容