【命题】
对于给定数 \(n\) ，求解其所有因子的欧拉函数值
本文不讨论朴素做法，仅讨论两种较为常用的求解方法
【法一】
根据公式 \(\boldsymbol \varphi(n)=n\prod_{i=1}^m (1-{1\over p_i})\)，其中 \(\displaystyle n=\prod_{i=1}^m p_i\)
对于 \(n\) 的每个因子 \(d\) ，暴力查询 \(\sqrt d\) 范围内的质因子，并筛除
最后核验 \(d\) 是否存在大于 \(\sqrt d\) 的质因子，若存在，则再计算该质因子贡献
复杂度为 \(O(\sqrt d)\)
int phid=d;
for(int i=2;i*i<=d;++i) if(d%i==0) {
while(d%i==0) d/=i;
phid=phid/i*(i-1);
}
if(d>1){
phid=phid/d*(d-1);
}
复杂度计算时，考虑 \(n\) 不大于 \(\sqrt n\) 的因子最多 \(\sqrt n\) 个，故不小于 \(\sqrt n\) 的因子与之成对出现，也不超过 \(\sqrt n\) 个
故每当出现 \(n\) 一个不大于 \(\sqrt n\) 的因子 \(d\) 时，我们对称考虑与它成对出现的因子 \({n\over d}\)
\(\displaystyle \quad T(n)\)
\(\displaystyle \leq\sum_{d=1}^{\sqrt n}(\sqrt d+\sqrt {n\over d})\)
\(\displaystyle =O(\int_1^{\sqrt n}\sqrt x\text dx)+\sqrt n\cdot O(\int_1^{\sqrt n}{1\over \sqrt x}\text dx)\)
\(\displaystyle =O(x^{3\over 2}|_1^{\sqrt n})+\sqrt n\cdot O(x^{1\over 2}|_1^{\sqrt n})\)
\(\displaystyle =O(n^{3\over 4})+O(n^{3\over 4})\)
\(\displaystyle =O(n^{3\over 4})\)
【法一优化】
由于复杂度计算时，不难发现，小于 \(\sqrt n\) 部分的因子和大于 \(\sqrt n\) 部分的因子复杂度贡献均为 \(O(n^{3\over 4})\)
根据质数定理的推论，\(n\) 范围内质数个数大约为 \({n\over \ln n}\)
故计算 \(n\) 的欧拉函数，仅需枚举 \(\sqrt n\) 范围内的质数，复杂度为 \(O({\sqrt n\over \ln\sqrt n})=O({\sqrt n\over \log n})\)
总求解复杂度如下：
\(\displaystyle \quad T(n)\)
\(\displaystyle \leq \sum_{d=1}^{\sqrt n}({\sqrt d\over \ln \sqrt d}+{\sqrt{n\over d}\over \ln \sqrt{n\over d}})\)
\(\displaystyle =O(\int_1^{\sqrt n}{2\sqrt x\over \ln x}\text dx)+O(\int_1^{\sqrt n}{2\sqrt {n\over x}\over \ln {n\over x}}\text d{n\over x})\)
\(\displaystyle =2\cdot O({1\over 3}\cdot \int_1^{\sqrt n} {\text dx^{3\over 2}\over \ln x^{3\over 2}})\)
\(\displaystyle =O(Li(({\sqrt n})^{3\over 2}))\)
\(\displaystyle =O(Li(n^{3\over 4}))\)
由于 \(\displaystyle \lim_{n\to +\infty} {Li(n)\over ({n\over \ln n})}=1\)
故 \(\displaystyle T(n)=O({n^{3\over 4}\over \ln n^{3\over 4}})=O({n^{3\over 4}\over \log n})\)
若额外考虑打出 \(m\) 范围内的欧拉函数值，显然 \(m\leq \sqrt n\) 时，对渐进复杂度无影响
当 \(m>\sqrt n\) 时，第二部分求解 \({n\over d}\) 时，上界修改为 \({n\over m}\)
故求解复杂度优化为 \(\displaystyle O(m+{({n\over m})^{3\over 2}\over \log {n\over m}})\)，其中 \(O(m)\) 为欧拉筛复杂度
由于欧拉筛往往被视为预处理，当计算上述结果 \(k\) 次时，每次的均摊复杂度为 \(\displaystyle O({m\over k}+{({n\over m})^{3\over 2}\over \log {n\over m}})\)
由均值不等式，当且仅当 \(\displaystyle {m\over k}={({n\over m})^{3\over 2}\over \log {n\over m}}\) ，即