数论分析---题解 【P2303 [SDOI2012] Longge 的问题】

题解已关。半年前做过的题目。 当时发现兔队的做法，没完全搞懂就过掉了。 现在回想一下还是不懂，然后自己推了几天，然后还原了。 感觉十分精妙的方法。 --- 求 $$\sum_{i=1}^n\gcd(i,n)$$ $n\leq 2^{32}$。 首先平凡的推导。 $$ \begin{aligned} \sum_{i=1}^n\gcd(i,n) &= \sum_{d|n}d\sum_{i=1}^n[\gcd(i,n)=d] \\ &= \sum_{d|n}d\sum_{i=1}^{n/d}[\gcd(i,\frac nd)=1] \\ &= \sum_{d|n}d\varphi(\frac nd) \end{aligned} $$ 此时就可以 $\mathcal O(d(n))$ 算。即，搜质因子的组合维护 $\varphi(\frac nd)$。 但是如果把 $\varphi(\frac nd)$ 按计算式展开，就不一样了。 记 $n$ 的唯一分解为 $$ n = \prod_{i=1}^mp_i^{c_i} $$ 其中 $p_i$ 是素数，$c_i>0$。 $$ \begin{aligned} \sum_{d|n}d\varphi(\frac nd) &= \sum_{d|n}d(\frac nd\prod_{p_i|\frac nd}(1-\frac 1{p_i})) \\ &= n\sum_{d|n}\prod_{p_i|\frac nd}(1-\frac 1{p_i}) \\ &= n\sum_{d|n}\prod_{p_i|d}f_i \end{aligned} $$ 此时。考虑 $d$ 为 $n$ 的所有约数时，后面的求积式有哪些可能取值。 显然，后面的式子只和素因子是否存在有关，而和其次数无关。 因此枚举存在的素因子集合 $t\subseteq s$，$s=\{1,2,\cdots,m\}$，取到该集合的次数是所有素因子次数之积。 $$ \begin{aligned} n\sum_{d|n}\prod_{p_i|d}f_i &= n\sum_{t\subseteq s}\prod_{i\in t}f_i\prod_{i\in t}c_i \\ &= n\sum_{t\subseteq s}\prod_{i\in t}f_ic_i \end{aligned} $$ 再考虑该式子。枚举子集，子集中元素相乘。 不难得到该式子等价于： $$ \begin{aligned} &\quad n\prod_{i=1}^m(1+f_ic_i) \\ &= n\prod_{i=1}^m[(1-\frac 1{p_i})c_i+1] \end{aligned} $$ 于是得到分解质因数复杂度的算法，即一般实现为 $\mathcal O(\sqrt n)$。 ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> typedef long long ll; inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } do x = x * 10 + ch - 48, ch = getchar(); while(ch >= '0' && ch <= '9'); return x * f; } int main() { ll n = read(), ans = n; for(register ll i = 2,c;i * i <= n;++i, c = 0) { while(!(n % i)) n /= i, ++c; ans = 1ll * c * (ans - ans / i) + ans; } if(n > 1) ans = 1ll * (ans - ans / n) + ans; std::printf("%lld\n",ans); return 0; } ```