bzoj2818 Gcd

· · 题解

写在前面

题目传送门：Hydro && gxyzoj

前置芝士

欧拉函数。

题意

令 P 为所有质数组成的集合。

给定正整数 N，求

\sum_{i = 1}^{N}\sum_{j = 1}^{N} \left [ \gcd(i, j) \in P \right ]

其中 \left [ ~ \right ] 表示艾弗森括号，当表达式 A 为真时，\left [ A \right ] 为 1，反之为 0。

思路

明显的一道数学题，但是需要了解一个知识点：欧拉函数和求 \sum_{i = 1}^{N}\sum_{j = 1}^{N} \gcd(i, j) 的公式。

如果了解欧拉函数，那么这道题就写完了（逃。我们只需要进行对欧拉函数的预处理后，求一个前缀和即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e7 + 5;
bool is_prime[N];
int pri[N], phi[N], sum[N];
int n, tot = 0, ans = 0;
void pre() {
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = 0, phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            pri[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && i * pri[j] <= n; j++) {
            is_prime[i * pri[j]] = 0;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
}

signed main() {
    scanf("%lld", &n);
    pre();
    for (int i = 1; i <= n; i++)
        sum[i] = phi[i] + sum[i - 1];
    for (int i = 1; i <= tot; i++)
        ans += sum[n / pri[i]] * 2 - 1;
    printf("%lld", ans);
    return 0;
}