《算法竞赛进阶指南》最大公约数 · 欧拉函数

题解

AcWing 220. 最大公约数(通俗易懂&效率高)

问

假设

则

所以题目等同于问在范围内，x与y互质的个数有多少对

对于每一个质数d，先不管互质条件，可以取到的数有：

然后问题转化为，问序列里互质的个数

对于一个数列而言，它的欧拉函数总和，就是两个互质数对个数

用前缀和统计每个素数d的能得到的对数，

又由于(x,y)是无序的，所以除了第一个$sum[1]$sum[1]，整个答案还需要*2

---

---

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10;
int n, m, K;

int prime[N], cnt, phi[N];
bool visP[N];

void get_euler(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!visP[i]) {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; i * prime[j] <= n; ++j) {
            visP[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

ll sum[N];

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    get_euler(n);
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + phi[i];
    }
    ll ans = 0;
    for (int i = 0; i < cnt; ++i) {
        int k = n / prime[i];
        ans += sum[k] * 2 - 1;//这里多算了一个sum[1] 还需要减去
    }
    cout <<ans << endl;

    return 0;
}