Luogu 1447 能量采集

题解

---

question

$$\sum_{x=1}^{n} \sum_{y=1}^{m} [2gcd(x,y)-1]$$

slove

不妨设 $n < m$
原式

$$=2\sum_{x=1}^{n} \sum_{y=1}^{m}gcd(x,y)-nm$$

令

$$f(d) = \sum_{x=1}^{n} \sum_{y=1}^{m} [gcd(x,y) = d]$$
令 $$F(d) = \sum_{x=1}^{n} \sum_{y=1}^{m} [d|gcd(x,y)]$$
then $$F(d) = \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor$$

then

$$F(d) = \sum_{n|d}f(d)$$
反演得 $$f(x) = \sum_{x|d} \mu (\frac{d}{x}) F(d)$$
考虑每个 $$F(d)$$ 当 $d > n$ 时的取值为 $0$,因为 $gcd(n,m)$ 的最大值为 $n$ 则
$$f(x) = \sum_{i=1}^{\lfloor \frac{n}{x} \rfloor} \mu(i) F(ix)$$
$$Ans = 2\sum_{x=1}^{n}xf(x)-mn = 2\sum_{x=1}^{n}x\sum_{i=1}^{\lfloor \frac{n}{x} \rfloor} \mu(i) \lfloor \frac{n}{ix} \rfloor \lfloor \frac{m}{ix} \rfloor - mn$$
对两部分分别整除分块

---

Code

#include <bits/stdc++.h>
const int N = 1e5 + 10;
#define LL long long
LL prime[N], mu[N], bo[N];
LL n, m;
void Get_mu() {
    mu[1] = 1;
    for(int i = 2; i <= N - 10; i ++) {
        if(!bo[i]) {prime[++ prime[0]] = i; mu[i] = -1;}
        for(int j = 1; j <= prime[0] && prime[j] * i <= N - 10; j ++) {
            bo[prime[j] * i] = 1;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            } else mu[i * prime[j]] = - mu[i];
        }
    }
    for(int i = 2; i <= N - 10; i ++) mu[i] += mu[i - 1];
}
LL Calc(LL n_, LL m_) {
    LL ret = 0;
    for(int i = 1, r; i <= n_; i = r + 1) {
        r = std:: min(n_ / (n_ / i), m_ / (m_ / i));
        ret += 1LL * (mu[r] - mu[i - 1]) * (n_ / i) * (m_ / i);
    }
    return ret;
}
int main() {
    Get_mu();
    std:: cin >> n >> m;
    if(n > m) std:: swap(n, m);
    LL Ans = 0;
    for(int i = 1, r; i <= n; i = r + 1) {
        r = std:: min(n / (n / i), m / (m / i));
        Ans += 1LL * (i + r) * (r - i + 1) / 2 * Calc(n / i, m / i);
    }
    std:: cout << 2 * Ans - n * m;
    return 0;
}