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

神仙反演...推了一晚上式子 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)

代码:

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
38
39
40
41
42
43
#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;
}
坚持原创技术分享,您的支持将鼓励我继续创作!