NOI 2010 做题笔记

xhgua's Blog / 2024-02-10 / 原文

NOI 2010 Day1 T1 能量采集

观察到 $(0, 0)$ 与 $(x, y)$ 连线上的整点个数正好是 $\gcd(x, y) - 1$（不包括端点），于是总能量损失即为：

\[\begin{aligned}{} & \sum\limits_{i = 1} ^ n\sum\limits_{j = 1} ^ m (2\times \gcd(i, j) - 1) \\ = &\ 2\times \sum\limits_{i = 1} ^ n\sum\limits_{j = 1} ^ m \gcd(i, j) - n\times m \end{aligned}\]

考虑如何计算二维 $\gcd$ 求和，根据 $\varphi * 1 = \text{id}$，反演得：

\[\begin{aligned}{} & \sum\limits_{i = 1} ^ n\sum\limits_{j = 1} ^ m \gcd(i, j) \\ = &\ \sum\limits_{i = 1} ^ n\sum\limits_{j = 1} ^ m \sum\limits_{d \mid \gcd(i, j)} \varphi(d) \\ = &\ \sum\limits_{d = 1} ^ n \varphi(d) \sum\limits_{i = 1} ^ n\sum\limits_{j = 1} ^ m [d\mid \gcd(i, j)] \\ = &\ \sum\limits_{d = 1} ^ n \varphi(d) \lfloor\dfrac{n}{d}\rfloor \lfloor\dfrac{m}{d}\rfloor \end{aligned}\]

于是线性筛出 $\varphi$ 即可，复杂度 $O(n)$。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1e5 + 5;

int n, m, tot;
int prime[N], phi[N];
bool isp[N];

void sieve() {
    memset(isp, true, sizeof(isp));

    isp[1] = false; phi[1] = 1;
    for (int i = 2; i < N; i++) {
        if (isp[i]) prime[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && 1ll * i * prime[j] < N; j++) {
            int p = prime[j];
            isp[i * p] = false;

            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            else phi[i * p] = phi[i] * (p - 1);
        }
    }
}

int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    sieve();

    std::cin >> n >> m;
    
    i64 ans = 0;
    for (int d = 1; d <= std::min(n, m); d++) 
        ans += 1ll * phi[d] * (n / d) * (m / d);

    std::cout << 2 * ans - 1ll * n * m << "\n";

    return 0;
}