Luogu1891 疯狂 LCM

发布于 14 天前  43 次阅读


Link

Sol

主要考察的是 gcdlcm 关系的一个性质: lcm(a, b) = \frac{a \times b}{gcd(a,b)}

那么我们用这个式子来替换现在的式子

\sum_{i=1}^{n} \frac{i \times n}{gcd(i,n)}

把乘的 n 这个常数项直接提到外面来,稍微改改

n \times \sum_{i=1}^{n} \frac{i}{gcd(i,n)}

常见套路:有整除,gcd,约数的时候,把枚举的东西改成枚举约数,再改成枚举倍数

那么我们先枚举约数试试

n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(i,n) = d]

再把中括号(布尔表达式)内的东西同时除一个 d

n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(\frac{i}{d}, \frac{n}{d}) = 1]

再写成枚举倍数的

n \times \sum_{d|n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i [gcd(i,\frac{n}{d}) = 1]

注意到因为 d|n,所以 \frac{n}{d}d 等价,全部改成枚举到 d

n \times \sum_{d|n} \sum_{i=1}^{d} i [gcd(i,d) = 1]

现在应该很显然, [gcd(i,d)=1] 就是 \varphi(d)

实际上因为 n 的约数是成对出现的,那么一共会有 \frac{d}{2} 对约数,直接把后面的东西利用这个性质算出来.

所以现在就是

n \times \sum_{d|n} \frac{\varphi(d)}{2} \times d

Code

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

#define int long long

const int SIZE = 1e6 + 5;

int T, n, tot;
int prime[SIZE], phi[SIZE], isPrime[SIZE], ans[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void euler()
{
    int siz = 1e6 + 1;
    phi[1] = isPrime[1] = 1;
    for (register int i = 2; i <= siz; ++ i) {
        if (!isPrime[i]) {
            prime[++ tot] = i, phi[i] = i - 1;
        }
        for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) {
            isPrime[i * prime[j]] = 1;
            if (i % prime[j])  phi[i * prime[j]] = phi[i] * phi[prime[j]];
            else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

signed main()
{
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    T = read();
    euler(); int siz = 1e6 + 1;
    for (int i = 1; i <= siz; ++ i) {
        for(int j = 1; i * j <= siz; ++ j) 
            ans[i * j] += (i == 1 ? 1 : 1ll * phi[i] * i / 2);
    }
    while (T --) {
        n = read();
        printf("%lld\n", ans[n] * n * 1ll);
        // puts("");
    }
    return 0;
}

朴实沉毅