神仙反演...推了一晚上式子 Link

简要题意

已知

$\begin{align}f(n) & = \sum _ {d | n} \gcd (d, {n \over d}) \\ F(n) & = \sum _ {i = 1} ^ n f(i)\end{align}$

求 $F(10^{15})$

GCD of Divisors

Every divisor $d$ of a number n has a complementary divisor $n/d$ .

Let $f(n)$ be the sum of the greatest common divisor of $d$ and $n/d$ over all positive divisors $d$ of $n$ , that is

$f(n)=\displaystyle\sum\limits_{d|n}\, \text{gcd}(d,\frac n d)$

Let $F$ be the summatory function of $f$ , that is

$F(k)=\displaystyle\sum\limits_{n=1}^k \, f(n)$

You are given that $F(10)=32$ and $F(1000)=12776$ .

Find $F(10^{15})$ .

题解

题目就是要求

$\begin{align} F(n) & = \sum _ {i = 1} ^ n f(i) \\ & = \sum _ {i = 1} ^ n \sum _ {d | i} \gcd (d, {i \over d})\end{align}$

然后反演套路 (枚举 $\gcd$ )

$\begin{align} F(n) & = \sum _ {i = 1} ^ n \sum _ {d | i} \gcd (d, {i \over d}) \\ & = \sum _ {c = 1} ^ n c \sum _ {i = 1} ^ n \sum _ {d | i} [\gcd (d, {i \over d}) = c]\end{align}$

注意到 $c | d$ 且 $c | {i \over d}$ , 所以有 $c^2 | i$ , 将这个提出来:

$\begin{align} F(n) & = \sum _ {c = 1} ^ n c \sum _ {i = 1} ^ n \sum _ {d | i} [\gcd (d, {i \over d}) = c] \\ & = \sum _ {c = 1} ^ n c \sum _ {i = 1} ^ {\left \lfloor {n \over c ^ 2} \right \rfloor} \sum _ {d | i} [\gcd(d, {i \over d}) = 1] \end{align}$

反演.

$\begin{align} F(n) & = \sum _ {c = 1} ^ n c \sum _ {i = 1} ^ {\left \lfloor {n \over c ^ 2} \right \rfloor} \sum _ {d | i} \sum _ {g | \gcd\left(d, {i \over d}\right)}\mu(g)\end{align}$

交换 $\sum$

$\begin{align} F(n) & = \sum _ {c = 1} ^ n c \sum _ {i = 1} ^ {\left \lfloor {n \over c ^ 2} \right \rfloor} \sum _ {d | i} \sum _ {g | \gcd\left(d, {i \over d}\right)}\mu(g) \\ & = \sum _ {c = 1} ^ n \sum _ {g = 1} ^ n c\times \mu(g)\sum _ {i = 1} ^ {\left \lfloor {n \over c ^ 2} \right \rfloor} \sum _ {d | i} [ g | \gcd (d, {i\over d})]\end{align}$

像上面一样提出 $g$ , 就有

$\begin{align} F(n) & = \sum _ {c = 1} ^ n \sum _ {g = 1} ^ n c\times \mu(g)\sum _ {i = 1} ^ {\left \lfloor {n \over c ^ 2} \right \rfloor} \sum _ {d | i} [ g | \gcd (d, {i\over d})] \\ & = \sum _ {c = 1} ^ n \sum _ {g = 1} ^ n c\times \mu(g)\sum _ {i = 1} ^ {\left \lfloor {n \over c ^ 2 g ^ 2} \right \rfloor} \sum _ {d | i} 1 \end{align}$

其中 $\sum _ {d | i} 1$ 正是 $\sigma_0$ (约数个数和)

由于 $I * \mu = e$ , $\text{id} = \varphi * I$

故 $\text{id} * \mu = (\varphi * I) * \mu = \varphi * (I * \mu) = \varphi$

所以考虑构造前面的卷积, 令 $q = c\times g$ . 注意到倒数第二个 $\sum$ 是枚举的范围, 故第一层只用枚举到 $\sqrt n$ 即可:

$\begin{align} F(n) & = \sum _ {c = 1} ^ \sqrt n \sum _ {g = 1} ^ n c\times \mu(g)\sum _ {i = 1} ^ {\left \lfloor {n \over c ^ 2 g ^ 2} \right \rfloor} \sum _ {d | i} 1 \\ & = \sum _ {q = 1} ^ \sqrt n \sum _ {g | q} g \times \mu \left(q\over g\right) \sum _ {i = 1} ^ {\left\lfloor n \over q ^ 2 \right\rfloor}\sigma _ 0 ( i ) \\ & = \sum _ {q = 1} ^ \sqrt n \varphi (q) \sum _ {i = 1} ^ {\left\lfloor n \over q ^ 2 \right\rfloor}\sigma _ 0 ( i ) \end{align}$

后面这个东西直接求就没了....实际上可以换枚举方式来解决:

$\sum _ {i = 1} ^ n \sigma _ 0 (i) = \sum _ { i = 1 } ^ n {\left \lfloor n \over i\right\rfloor}$

后面的式子就可以每次 $O(\frac {\sqrt n} q)$ 做, 对 $q$ 求和就是相当于一个调和级数, 所以时间复杂度就是 $O(\sqrt n\ln \sqrt n)$

代码:

#include <bits/stdc++.h>

#define int long long

const int N = 31622777 + 10; // sqrt(1e15)

int cnt;
int pri[N];
int mu[N + 10];
int phi[N + 10];
bool vis[N + 10];

void pre (int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) pri[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; j++) {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) { phi[i * pri[j]] = phi[i] * pri[j]; break; }
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
}

int sum (int x) {
    int ret = 0;
    for (int l = 1, r; l <= x; l = r + 1) {
        r = x / (x / l);
        ret += (r - l + 1) * (x / l);
    }
    return ret;
}

signed main () {
    int n, ans = 0;
    n = 1000000000000000ll;
//    scanf("%lld", &n);
    int limit = sqrt(n) + 1;
    pre(limit);
    for (int i = 1; i <= limit; i++) ans += phi[i] * sum(n / (i * i)); 
    printf("%lld", ans);
    return 0; 
}

「PE#530」GCD of Divisors - 莫比乌斯反演

简要题意

GCD of Divisors

题解