浅谈欧拉繁衍的证明及例题
Ayano_
·
·
个人记录
果果要求掌握的东西当然是要掌握的咯。
最终形式
\Large{n=\sum_{d|n}^{}}{\varphi(d)}
证明
\large\because n=\sum_{d|n}\sum_{j=1}^{n}{[\gcd(j,n)=d]}
解释一下，首先，这里的 \gcd(j,n) 一定是只有一个值，不可能说有两个不同的值来自同一个 \gcd(j,n) ；其次，为什么这一坨东西等于 n 呢，因为其一说的每个 \gcd 都有唯一确定的值，因此我们只需要枚举 \gcd 的每种可能并枚举所有 n 以内的正整数就必然有且仅有一种可能的 d 满足每组 \gcd(j,n)=d 。
换句话说，因为一个 \gcd(j,n) 只对应唯一一个 d ，这里我们把所有可能的 \gcd 的值和所有的 j 都枚举了自然其值也就等于 n 了（主要就是说明一个不重也不漏）。
\large\therefore \ n=\sum_{d|n}\sum_{j=1}^{\frac{n}{d}}{[\gcd(j,\frac{n}{d})=1]}
这里没什么好说的，目的是把 \gcd 的值化为 1 后能转化成欧拉函数的形式。
\large\therefore n=\sum_{d|n}{\varphi(\frac{n}{d})}
\large\therefore n=\sum_{d|n}{\varphi(d)}
这里是因为每个 \frac{n}{d} 和 d 是对应的，所以能如此转化。
例题
- 多组数据，每组数据给出一个数 n ，求 \sum_{i=1}^{n}{\gcd(i,n)} 。
利用欧拉反演，改变题目公式如下：
\sum_{i=1}^{n}{\sum_{d|\gcd(i,n)}{\varphi(d)}}
拆开 \gcd 得：
\sum_{i=1}^{n}{\sum_{d|i,d|n}{\varphi(d)}}
改变循环顺序得：
\sum_{d|n}\varphi(d)\sum_{i=1}^{n}[d|i]
化简得：
\sum_{d|n}\varphi(d)\frac{n}{d}
关于推导式子就没了。这时只需将 \text{phi} 预处理，每次询问 \sqrt{n} 复杂度。
先排序，可得以下原公式：
\sum_{i=1}^{n}\sum_{j=1}^{i-1}\gcd(a_i,a_j)(n-i)
带入欧拉反演如下：
\sum_{i=1}^{n}\sum_{j=1}^{i-1}(\sum_{d|\gcd(a_i,a_j)}{\varphi(d)})(n-i)
化简：
\sum_{i=1}^{n}(n-i)\sum_{j=1}^{i-1}\sum_{d|a_i,d|a_j}{\varphi(d)}
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\cdot cnt_{d}
其中我们可以边枚举 i 边处理 cnt_d ，并预处理 \varphi(x) 。因此总时间复杂度为 O(M+TN\sqrt{M}) ， M 表示 a_i 的值域，还会有一些小常数，会有点卡常。