题目链接：LOJ 6229

这是一道非常简单的数学题。

最近 LzyRapx​ 正在看 mathematics for computer science 这本书，在看到数论那一章的时候，LzyRapx 突然想到这样一个问题。

设

$$ F(n) = \sum_{i = 1} ^ n \sum_{j = 1} ^ i \frac{\operatorname{lcm}(i, j)}{\gcd(i, j)} $$

其中，$\operatorname{lcm}(a, b)$ 表示 $a$ 和 $b$ 的最小公倍数，$\gcd(a, b)$ 表示 $a$ 和 $b​$ 的最大公约数。

给定 $n$ ，让你求： $F(n) \bmod (10 ^ 9 + 7)​$。

数据范围：$1 \le n \le 10 ^ 9$。

Solution

由于 $j$ 的上界为 $i$，处理起来比较麻烦，我们将其上界强行转化为 $n$，那么最终的答案为 $\frac{F(n) + n}{2}$。

接下来就是愉快的推式子时间啦！

$$ \begin{align*} F(n) & = \sum_{i = 1} ^ n \sum_{j = 1} ^ n \frac{\operatorname{lcm}(i, j)}{\gcd(i, j)} \\ & = \sum_{i = 1} ^ n \sum_{j = 1} ^ n \frac{i \cdot j}{\gcd(i, j) ^ 2} \\ & = \sum_{d = 1} ^ n \sum_{i = 1} ^ n \sum_{j = 1} ^ n [\gcd(i, j) = d] \frac{i \cdot j}{d ^ 2} \\ & = \sum_{d = 1} ^ n \sum_{i = 1} ^ {\left\lfloor\frac{n}{d}\right\rfloor} \sum_{j = 1} ^ {\left\lfloor\frac{n}{d}\right\rfloor} [\gcd(i, j) = 1] i \cdot j \\ & = \sum_{d = 1} ^ n \sum_{i = 1} ^ {\left\lfloor\frac{n}{d}\right\rfloor} \sum_{j = 1} ^ {\left\lfloor\frac{n}{d}\right\rfloor} i \cdot j \sum_{p \mid i, p \mid j} \mu(p) \\ & = \sum_{p = 1} ^ n \mu(p) \sum_{d = 1} ^ n \sum_{i = 1} ^ {\left\lfloor\frac{n}{d}\right\rfloor} \sum_{j = 1} ^ {\left\lfloor\frac{n}{d}\right\rfloor} [p \mid i] \cdot [p \mid j] \cdot i \cdot j \\ & = \sum_{p = 1} ^ n \mu(p) \cdot p ^ 2 \sum_{d = 1} ^ {\left\lfloor\frac{n}{p}\right\rfloor} S\left(\left\lfloor\frac{n}{dp}\right\rfloor\right) ^ 2 \Longrightarrow S(n) = \sum_{i = 1} ^ n i \\ & = \sum_{i = 1} ^ n S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) ^ 2 \sum_{d \mid i} \mu(d)\cdot d ^ 2 \\ \end{align*} $$

上述部分是简单的莫比乌斯反演，具体过程不再赘述。

目前的式子已经可以 $\mathcal O(n \log n)$ 求解了。接下来的优化思路肯定是对 $S$ 数论分块，但是瓶颈为 $\sum_{d \mid i} \mu(d) \cdot d ^ 2$ 的前缀和。很自然地，我们会想到杜教筛。

看到 $\mu(d) \cdot d ^ 2$ 这个东西，肯定会想到卷上一个 $g(x) = x ^ 2$ 函数。但是又发现 $f$ 本身也是一个卷积形式，设：

$$ t(x) = \mu(x) \cdot x ^ 2 $$

可以发现 $f$ 函数为：

$$ f = t \ast 1 $$

构造 $h$ 为 $f$ 和 $g$ 的卷积：

$$ \begin{align*} h & = f \ast g \\ & = (t \ast 1) \ast g \\ & = t \ast g \ast 1 \\ & = e \ast 1 \\ & = 1 \end{align*} $$

很惊喜的发现 $h$ 是一个常函数！因为 $t$ 是积性函数，那么 $f = t \ast 1$ 也是积性函数，可以直接线性筛。

直接按照套路上杜教筛就行啦。

时间复杂度：$\mathcal O(n ^ {\frac{2}{3}})$。

Code

#include <cstdio>
#include <unordered_map>

const int N = 2e6 + 5, LIM = 2e6;
const int P = 1e9 + 7, inv2 = 500000004, inv6 = 166666668;

int n, tot, p[N], d[N], f[N], s[N];
bool flg[N];
std::unordered_map<int, int> S;

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += P);
}
void sieve(int n) {
    std::fill(flg + 1, flg + n + 1, true);
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (flg[i]) {
            p[++tot] = i, f[i] = 1 - 1LL * i * i % P;
        }
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            flg[i * p[j]] = false;
            if (i % p[j] == 0) {
                f[i * p[j]] = f[i];
                break;
            } else {
                f[i * p[j]] = 1LL * f[i] * f[p[j]] % P;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (f[i] < 0) f[i] += P;
        add(s[i] = f[i], s[i - 1]);
    }
}
int F(int n) {
    if (n <= LIM) return s[n];
    if (S.find(n) != S.end()) return S[n];
    int ans = n;
    auto G = [](int n) {
        return 1LL * n * (n + 1) % P * (n + n + 1) % P * inv6 % P;
    };
    for (int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        sub(ans, 1LL * (G(r) - G(l - 1) + P) * F(n / l) % P);
    }
    return S[n] = ans;
}
int main() {
    sieve(LIM);
    scanf("%d", &n);
    int ans = 0;
    auto S = [](int n) {
        return 1LL * n * (n + 1) % P * inv2 % P;
    };
    for (int l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        int t = S(n / l);
        add(ans, 1LL * t * t % P * (F(r) - F(l - 1) + P) % P);
    }
    printf("%d\n", 1LL * (ans + n) * inv2 % P);
    return 0;
}