2020-02-28 17:52 山东大学 C++

关注

「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)$

代码:

#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; 
}

Shq的题解专栏文章被收录于专栏

之前的一些文章，来搬(chao)运(leng)下(fan)，可能会再更新一些文章

全部评论

推荐最新楼层

04-20 11:57

重庆大学 Java

0实习，我是怎么拿到大厂暑期实习offer的

一些个人见解，主要是记录下找暑期的感受，希望下面的建议能帮到别人。如果你是顶2/末9以下，现在还是0实习的话，我认为可以准备考研或先投投小厂等秋招再战。1.海投，在暑期投了大概20多家吧，对于我0实习末9本的bg，简历不过筛是常有的事，所以最重要的就是得海投。2.项目，我最后简历上写的是点评+外卖和AI对话两个项目，实际面试中感觉对项目的提问占比非常大，所以一定要把项目摸透。另外最好还是得有个和AI相关的项目，最好知道评价项目的量化指标（比如RAG召回率、准确率，响应时间之类的），让你跟面试官有的聊。强烈建议去看看讲解Claude Code泄露的讲解视频，我现在的公式吟唱就是“我现在的某个模块...

发面经攒人品

点赞评论收藏

04-19 13:34

北京邮电大学 Java

字节 TikTok-Shop 后端开发二面

自我介绍实习除了 Coze，了解过其他 Agent 相关框架吗？比如 LangChain、LangGraph三个系统都涉及 DAG，区别是什么Coze 的执行引擎能否支撑你的系统A 系统 利用编排实现解耦，还有没有其他提升空间2k QPS 下，MySQL 可以抗住，为什么加二级缓存相比加缓存之前，性能提升了多少B 平台 针对下游模型的 TPM、QPM 限制，如何限流处理在采用令牌桶的基础上，任务具有不同的优先级，如何处理；再增加一个租户维度（多业务），如何处理视频生成后的链路关注过吗？最终的视频是否满足预期八股为什么选择 Redis 做缓存，还有什么应用场景Redis 实现分布式锁的原理是什么...

查看16道真题和解析

点赞评论收藏

03-03 23:12

已编辑

北京邮电大学 Java

27届找暑期，简历求拷打

书海为家：我来给一点点小建议，因为毕竟还在学校不像工作几年的老鸟有丰富的项目经验，面试官在面试在校生的时候更关注咱们同学的做事逻辑和思路，所以最好在简历中描述下自己做过项目的完整过程，比如需求怎么来的，你对需求的解读，你想到的解决办法，遇到困难如何找人求助，最终项目做成了什么程度，你从中收获了哪些技能，你有什么感悟。

你的简历改到第几版了

点赞评论收藏