題解 luogu P2568 GCD

題解 luogu P2568 GCD

時間：2019.3.11

歐拉函數+前綴和

題目描述

給定整數\(N\)，求\(1\le x,y \le N\)且\(\gcd(x,y)\)為素數的數對\((x,y)\)有多少對.

分析

枚舉素數\(p\), 先求出\(1\le x,y \le \left \lfloor \dfrac n p \right \rfloor\)且\(\gcd(x, y) = 1\)的數對\((x,y)\)有多少對，然后再將\(x,y\)同時乘以\(p\)即可.

不妨欽定\(x \le y\)，如果知道了\(y\)，那么\(x\)的數量就是\(\varphi(y)\)（\(\text{phi(y)}\)）個。對于\(x \ge y\)同理。

注意數對\((1, 1)\)會被計算兩次，答案要減一。

代碼

#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 10000000 + 10;
typedef long long LL;
bool is_prime[kMaxN];
int phi[kMaxN];
int prime[kMaxN], top;
int n;
long long ans, phi_sum[kMaxN];
void Sieve() {memset(is_prime, true, sizeof(is_prime));top = 0;phi[1] = 1;for (int i = 2; i <= n; i++) {if (is_prime[i]) {prime[++top] = i;phi[i] = i - 1;}for (int j = 1; j <= top && 1ll * i * prime[j] <= n; j++) {int p = prime[j];is_prime[i * p] = false;phi[i * p] = phi[i] * (i % p ? p - 1 : p);if (i % p == 0) break;}}
}
int main() {scanf("%d", &n);Sieve();for (int i = 1; i <= n; i++) {phi_sum[i] = phi_sum[i - 1] + phi[i];}for (int i = 1; i <= top; i++) {ans += phi_sum[n / prime[i]] * 2 - 1;}printf("%lld\n", ans);return 0;
}