「LOJ 6686」Stupid GCD（数论）

题目大意

「LOJ 6686」Stupid GCD

求下列式子的值：

$$\sum_{i = 1}^{n} \gcd(\lfloor \sqrt[3]{i} \rfloor, i)$$

数据范围：$n \le 10^{30}$。

思路分析

Siyuan 太强啦 QwQ

先枚举 $\sqrt[3]i$ 的值：

$$\begin {align*} & \sum_{i = 1}^{n} \gcd(\lfloor \sqrt[3]{i} \rfloor, i) \\ = & \sum_{i = 1}^{\lfloor \sqrt[3]{n} \rfloor} \sum_{j = i^3}^{\min\{n, i ^ 3 + 3i^2 + 3i\}}\gcd(i, j) \\ = & \color{green}{\sum_{i = \lfloor \sqrt[3]{n} \rfloor^3}^{n} \gcd(\lfloor \sqrt[3]{n} \rfloor, i)} + \color{purple}{\sum_{i = 1}^{\lfloor \sqrt[3]{n} \rfloor - 1} \sum_{j = 0}^{3i^2 + 3i}\gcd(i, j)} \\ \end {align*}$$

考虑子问题：

$$\begin {align*} & \sum_{i = 1}^{n} \gcd(m, i) \\ = & \sum_{d} d \sum_{i = 1}^{n} [\gcd(m, i) = d]\\ = & \sum_{d | m} d \sum_{td | m, td | i} \mu(t) \\ = & \sum_{T | m} \lfloor \frac{n}{T}\rfloor \sum_{d | T} d \cdot \mu(\frac{T}{d}) \\ = & \sum_{T | m} \lfloor \frac{n}{T} \rfloor \varphi(T) \end {align*}$$

考虑计算绿色部分：

$$\begin {align*} & \color{green}{\sum_{i = \lfloor \sqrt[3]{n} \rfloor^3}^{n} \gcd(\lfloor \sqrt[3]{n} \rfloor, i)} \\ = & \sum_{i = \lfloor \sqrt[3]{n} \rfloor^3}^{n} \gcd(\lfloor \sqrt[3]{n} \rfloor, i) \\ = & \sum_{i = 0}^{n - \lfloor \sqrt[3]{n} \rfloor^3} \gcd( \lfloor \sqrt[3]{n} \rfloor, i) \end {align*}$$

枚举 $\lfloor \sqrt[3]n \rfloor$ 的因数，递归计算 $\varphi$ 值即可。时间复杂度 $O(n^{\frac{1}{6}})$。

再考虑计算紫色部分。令 $m = \lfloor \sqrt[3]n \rfloor - 1$，得：

$$\begin {align*} & \color{purple}{\sum_{i = 1}^{\lfloor \sqrt[3]{n} \rfloor - 1} \sum_{j = 0}^{3i^2 + 3i}\gcd(i, j)} \\ = & \sum_{i = 1}^{m} \sum_{j = 0}^{3i^2 + 3i}\gcd(i, j) \\ = & \frac{m \cdot (m + 1)}{2} + \sum_{i = 1}^{m} \sum_{T | i} \lfloor \frac{3i^2 + 3i}{T} \rfloor \cdot \varphi(T) \\ = & \frac{m \cdot (m + 1)}{2} + \sum_{T = 1}^{m}\varphi(T) \sum_{i = 1}^{\lfloor \frac{m}{T} \rfloor} \frac{3T^2i^2 + 3Ti}{T} \\ = & \frac{m \cdot (m + 1)}{2} + 3 \sum_{T = 1}^{m} \varphi(T) \sum_{i = 1}^{\lfloor \frac{m}{T} \rfloor} Ti^2 + i \\ = & \frac{m \cdot (m + 1)}{2} + 3 \cdot (\sum_{T = 1}^{m} \varphi(T) \cdot T \sum_{i = 1}^{\lfloor \frac{m}{T} \rfloor} i^2) + 3 \cdot (\sum_{T = 1}^{m} \varphi(T) \cdot \sum_{i = 1}^{\lfloor \frac{m}{T}\rfloor} i) \\ \end {align*}$$

使用整除分块 + 杜教筛即可做到 $O(n^\frac{2}{9})$。

代码实现

#include <bits/stdc++.h>