Solution - P2303 [SDOI2012] Longge 的问题

P2303 [SDOI2012] Longge 的问题

idea:

推式子。

解决方案：

直接开推：

$$\sum_{i=1}^n\gcd(i,n) = \sum_{d\mid n}d\sum_{d\mid i}^n [\gcd(i,n)=d] = \sum_{d\mid n}d\sum_{i=1}^{\frac{n}{d}} [\gcd(i,\frac{n}{d})=1] = \sum_{d\mid n}d\cdot\varphi(\frac{n}{d})$$

这个式子已经可以用了：我们求出 $n$ 的所有质因子，然后 $Dfs$ 枚举 $n$ 的因子即可。时间复杂度 $O(\sqrt n + k)$ 。 $k$ 为 $n$ 的因子数。由于 $O(k) = O(\sqrt n)$ ，时间复杂度是 $O(\sqrt n)$ 的。

然而我们可以再进一步优化（参考题解）

$$\sum_{d\mid n}d\cdot\varphi(\frac{n}{d}) = \sum_{d\mid n}\frac{n}{d}\cdot\varphi(d) = \sum_{d\mid n}\frac{n}{d}\cdot d\prod_{p\mid d,p\in\mathbb{P}} \frac{p-1}{p} = n\cdot\sum_{d\mid n}\prod_{p\mid d,p\in\mathbb{P}} \frac{p-1}{p}$$

将 $n$ ，$d$ 分解：

$$n = \prod_{i=1}^k p_i^{a_i}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

$$d = \prod_{i=1}^k p_i^{b_i}(b_i\in[0,a_i])$$

那么 $d$ 的答案是：

$$res_d = \prod_{i=1}^k \frac{p_i-1}{p_i}[b_i\neq 0]$$

那么可以发现，与 $d$ 答案相同的其他数只需要包含相同的质因数即可，和个数无关。不妨设 $d$ 有 $g$ 个不同的质因子，第 $i$ 个质因子为 $q_i$ 。对于和 $d$ 一类的数答案的和为：

$$ans_d = (\prod_{i=1}^g \frac{q_i-1}{q_i})(\prod_{i=1}^g a_{pos(i)}) = \prod_{i=1}^g \frac{q_i-1}{q_i}\cdot a_{pos(i)}$$

对于 $n$ 的每个质因子，都可以有选和不选两种原则。故答案为：

$$\sum (\frac{p_1-1}{p_1}\cdot a_1)^{0/1}\cdot (\frac{p_2-1}{p_2}\cdot a_2)^{0/1}...(\frac{p_k-1}{p_k}\cdot a_k)^{0/1}$$

只能意会。。。相当于 $\Sigma$ 里面有 $2^n$ 项。然后我们可以因式分解，答案为：

$$\prod_{i=1}^k (\frac{p_i-1}{p_i}\cdot a_i +1)$$

其实很好理解，每个质因子都可以选和不选，选的话是前面一坨，不选是 $1$ ，乘开来刚好是 $2^n$ 项。

用这个式子可以做到时间上 $O(\sqrt n)$ 的复杂度，空间上 $O(1)$ 。