题解：P2303 [SDOI2012] Longge 的问题
LTTXiaochuan
·
·
题解
本篇题解是对小粉兔题解最终计算式推导的补充证明，用公式详细阐明了兔队省略的公式变形、因式分解等过程，阅读前请您确保您已经了解了兔队的题解以及常规做法。
我们已经有下式
\sum\limits_{j|n}j\sum\limits_{i=1}^{\frac{n}{j}}[\gcd(i,\frac{n}{j})=1]=\sum_{j|n}j\times\phi(\frac{n}{j})
接下来继续推导。
狄利克雷卷积
观察到上式
\sum_{j|n}j\times\phi(\frac{n}{j})
实际上就是一个狄利克雷卷积。什么是狄利克雷卷积？
设 f 和 g 是算术函数，记 f 和 g 的狄利克雷卷积为 f*g，定义为：
(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})
狄利克雷卷积有如下性质：
-
交换律：f*g=g*f；
-
结合律：(f*g)*h=f*(g*h)；
-
分配率：f*(g+h)=(f*g)+(f*h)；
-
定义元函数 \varepsilon(n)=[\frac{1}{n}]，则 \forall f，\varepsilon*f=f*\varepsilon=f；
-
两个积性函数的狄利克雷卷积仍是积性函数。
利用其中的第五条性质，我们定义 \displaystyle F(n)=\sum_{j|n}j\times \phi(\frac{n}{j})，则 F(n) 显然也是积性函数。
由
n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}
则有
F(n) = F(p_1^{a_1}) F(p_2^{a_2}) \cdots F(p_k^{a_k})
又由
F(p^a) = \sum_{d|p^a} d \cdot \phi(\frac{p^a}{d})
由欧拉函数的定义得
\phi(p^a) = p^a - p^{a-1}
又显然有
d=\{1,p,2p,\cdots,p^a\}
故
\begin{align*}
F(p^a) &= (p^a - p^{a-1}) + p(p^{a-1} - p^{a-2}) + \cdots + p^{a-1}(p^1 - p^0) + p^a \cdot 1 \\ &= (p^a - p^{a-1}) + (p^a - p^{a-1}) + \cdots + (p^a - p^{a-1}) + p^a \\ &=(a+1)p^a-ap^{a-1} \\ &=p^a(\frac{pa+p-a}{p})
\end{align*}
于是
\begin{align*}
F(n)&=\prod_{i=1}^k p^{a_k} \times \prod_{i=1}^k(\frac{p_ia_i+p_i-a_i}{p_i})
\\&=n\prod_{i=1}^k(\frac{p_ia_i+p_i-a_i}{p_i})
\end{align*}
证毕。