原题链接:Acwing220

题目描述:给定整数 $N$,求 $1 \le x,y \le N$ 且 $GCD(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

数据范围:$ 1 \le N \le 10^7$

欧拉函数,互质数对个数

推公式

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

即对于每个质数 $p$ ,满足 $gcd(x,y)=p$ 的数对 $(x,y)$ 的个数,等价于 $1 \le x,y \le \frac{N}{p}$ 且 $(x,y)$ 互质的数对个数。可以参考 Acwing201可见的点 一题。对于质数 $p$ 满足条件的数对个数为:$(\varphi(2)+..+\varphi(\frac{N}{p})) \times 2 + 1$。

可以预处理出,欧拉函数 $\varphi(x)$ 的前缀和,特殊规定 $\varphi(1)=0$。枚举每一个质数,累加到答案中即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 10000010;

int n;
int primes[N], cnt;
bool st[N];
LL phi[N], s[N];

void euler(int n) {
    // phi[1] = 1; 特殊规定为0
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + phi[i];
}

int main() {
    cin >> n;
    euler(n);
    LL res = 0;
    for (int i = 0; i < cnt; i++) res += s[n / primes[i]] * 2 + 1;
    cout << res << endl;
    return 0;
}