最大公约数

原题链接

题目描述

给定整数 \(N\)，求 \(1≤x,y≤N\) 且 \(\gcd(x,y)\) 为素数的数对 \((x,y)\) 有多少对。

\(\gcd(x,y)\) 即求 \(x，y\) 的最大公约数。

---

欧拉函数

\(\gcd(x,y)=p\iff \gcd(\frac{x}{p},\frac{y}{p})=1\)

即，求 \(\gcd(x',y')=1\quad{x',y'\in[0,\frac{N}{p}}]\)。

根据 可见的点 推出的公式，\(res=\displaystyle \sum_{p\in Prime}\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor}2\varphi(i)-1\)

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 10000010;

int n;
vector<int> prime;
LL s[N], phi[N];
bool st[N];

void init(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            phi[i] = i - 1;
            prime.push_back(i);
        }

        for (int j = 0; prime[j] * i <= n; j++) {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }

    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + phi[i];
}

int main() {
    cin >> n;
    init(n);

    LL res = 0;
    for (auto p : prime) {
        res += 2 * s[n / p] - 1;
    }
    cout << res << endl;

    return 0;
}