[bzoj 2226][spoj 5971] lcmsum

题目大意

给定 (n) ，求 [
sum_{i = 1}^{n} lcm(i, ; n)
] 多组询问。

(1 leqslant T leqslant 300,000)

(1 leqslant n leqslant 1,000,000)

题目链接

BZOJ 2226

SPOJ 5971 - LCMSUM

题解

[
begin{align}
&sum{i = 1}^{n} lcm(i, ; n) \
= &sum{i = 1}^{n} frac{n i}{gcd(i, ; n)} \
= &n sum{i = 1}^{n} frac{i}{gcd(i, ; n)} \
= &n sum{d | n} frac{1}{d} sum{i = 1}^{n} [gcd(i, ; n) = d] i \
= &n sum{d | n} frac{1}{d} sum{i = 1}^{lfloor frac{n}{d} rfloor} [gcd(i, ; lfloor frac{n}{d} rfloor) = 1] i d \
= &n sum{d | n} sum_{i = 1}^{lfloor frac{n}{d} rfloor} [gcd(i, ; lfloor frac{n}{d} rfloor) = 1] i \
end{align}
]

记后面的和式为 (f(i))，由于当 (n > 1) 时，如果有 (gcd(n, ; x) = 1)，则有 (gcd(n, ; n - x) = 1)，所以与 (n) 互质的数是成对出现的，所以有： [
f(i) =
begin{cases}
1 qquad n = 1 \
frac{n varphi(n)}{2} qquad n > 1
end{cases}
] 此时答案为 (n sum_{d | n} f(d))，枚举约数，每次询问复杂度大概是 (O(sqrt{n}))，考虑进一步优化。

把 (f(i)) 放回去，(d = 1) 时补上一个 (1)，则答案为： [
n (sum{d | n} lfloor frac{d varphi(d)}{2} rfloor + 1) = frac{n}{2} (sum{d | n}dvarphi(d) + 1)
] 发现 (g(n) = sum_{d | n} d varphi(d)) 具有积性，但我不会推式子。。。

虽然做不到 (O(n)) 预处理，但 (O(n log n)) 的预处理也够过了。

明明都是小学开始接触的东西，为什么一到了反演，lcm 就比 gcd 复杂了这么多。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

const int MAXN = 1000005;
long long phi[MAXN], f[MAXN];
int prime[MAXN], primeCnt;
bool notPrime[MAXN];
void () {
    notPrime[0] = notPrime[1] = true;
    phi[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        if (!notPrime[i]) {
            prime[++primeCnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= primeCnt && i * prime[j] < MAXN; j++) {
            notPrime[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for (int i = 1; i < MAXN; i++) for (int j = i; j < MAXN; j += i) f[j] += i * phi[i];
}
long long calc(int n) {
    return n * (f[n] + 1) / 2;
}
int main() {
    shaker();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%lldn", calc(n));
    }
    return 0;
}