BZOJ 2226 - [Spoj 5971] LCMSum

#数学 #数论 #欧拉函数 #线性筛

Published on 2017-01-20

描述

给定 $n(n\le {10}^7)$ ，请你求：

\sum_{1\le i\le n}\mathrm{lcm}(i, n)

有组询问。

分析

通常 $\mathrm{lcm}$ 需要化为 $\gcd$ ：

\sum_{1\le i\le n}\frac {n \cdot i} {\gcd(i, n)}

枚举 $\gcd$ 为 $d$ ，化简一番：

设 $f(n)$ 为内层和式的值，则考虑快速求 $f(n)$ ：

f(n) = \sum_{i = 1}^n[\gcd(i, n) = 1]\cdot i

我们考虑对于 $n\ge 3$ ，如果有 $\gcd(n, x) = 1$ ，必然有 $\gcd(n, n - x) = 1$ （根据欧几里得算法），所以中与 $n$ 互质的数必然是成对出现的，那么 $f(n)$ 就可求出：

至此可以 $O(n)$ 预处理出 $\varphi(n)$ ，枚举 $n$ 的约数来 $O(\sqrt n)$ 回答单组询问。但是时间仍然难以承受。

这种题中，降低时间复杂度的方法无非就是预处理，我们考虑答案的形式：

n\sum_{d \mid n}f(d)

由于 $d = 1$ 时需要特判，很烦人，我们单独考虑，由于 $\varphi(1)\cdot 1 = 1$ ，缺一个 $1$ ，补上即可，那么式子化简为：

\frac n 2(1 + \sum_{d \mid n}\varphi(d) \cdot d)

设 $g(n) = \sum_{d \mid n}\varphi(d) \cdot d$ ，那么我们就可以用欧拉筛来 $O(n\log n)$ 的预处理出所有的 $g(n)$ ，这样就可以 $O(1)$ 的回答询问了。

我们注意到 $g(n)$ 是有积性的，原因是 $\varphi(n) \cdot n$ 有积性，而对于一个积性函数 $m(n)$ 来说：

\sum_{d \mid n}m(d)

也是积性的，所以 $g(n)$ 是有积性的，于是可以线筛 $O(n)$ 预处理出所有的 $g(n)$ （代码里面写的是欧拉筛）。

代码

//  Created by Sengxian on 2017/01/19.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 2226 欧拉筛
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000000 + 3;
int primes[MAX_N], cnt = 0;
bool isPrime[MAX_N];
int phi[MAX_N];
ll f[MAX_N];

void prepare() {
    fill(isPrime + 2, isPrime + MAX_N, true);
    phi[1] = 1;
    for (int i = 2; i < MAX_N; ++i) {
        if (isPrime[i]) primes[cnt++] = i, phi[i] = i - 1;
        for (int j = 0; j < cnt && primes[j] * i < MAX_N; ++j) {
            int t = primes[j] * i;
            isPrime[t] = false;
            if (i % primes[j] == 0) {
                phi[t] = phi[i] * primes[j];
                break;
            } else {
                phi[t] = phi[i] * (primes[j] - 1);
            }
        }
    }

    for (int i = 1; i < MAX_N; ++i)
        for (int j = i; j < MAX_N; j += i)
            f[j] += (ll)phi[i] * i;
}

inline ll solve(int n) {
    if (n == 1) return 1;
    else if (n == 2) return 4;
    ll res = f[n] + 1;
    return res * n / 2;
}

int main() {
    prepare();

    int caseNum = readInt();
    while (caseNum--) printf("%lld\n", solve(readInt()));
    return 0;
}

BZOJ 2749 - [HAOI2012]外星人 BZOJ 2302 - [HAOI2011]Problem c

Sengxian's Blog

BZOJ 2226 - [Spoj 5971] LCMSum

描述

分析

代码