Contest5408 - 数论函数
Published:
A gcd
\[\begin{aligned} & \sum\limits_{i=1}^n \sum\limits_{j=1}^n [\gcd(i,j) \in P] \\ =& \sum\limits_{d=1}^n [d \in P] \sum\limits_{i=1}^n \sum\limits_{j=1}^n [\gcd(i,j) = d] \\ =& \sum\limits_{d=1}^n [d \in P] \sum\limits_{i=1}^{\lfloor \frac n d \rfloor} \sum\limits_{j=1}^{\lfloor \frac n d \rfloor} [\gcd(i,j) = 1] \\ =& \sum\limits_{d=1}^n [d \in P] \times (2 S_\varphi(\lfloor \frac n d \rfloor) - 1) \\ \end{aligned}\]时间复杂度 $\Theta(n)$。
B 完全平方数
洛谷原题 P4318 完全平方数。
C 欧拉函数
简要题意：给定一个数 $n$ 的唯一分解 $\prod\limits_{i=1}^m p_i^{q_i}$，求 $n \leftarrow \varphi(n)$ 几次能使 $n = 1$。$p_i \le 10^5, q_i \le 10^9, m \le 2000$。$50$ 组数据。
打表找规律，注意到最终总会是 $2^x$ 在迭代，因此考虑数 $2$ 的个数。
令 $f_p$ 为 $p$ 能贡献的 $2$ 的个数。
| $f_2 = 1$，$f_p = \sum\limits_{q | (p-1)} f_q$，其中 $q$ 为质数，且可以重复。 |
$f$ 可以直接线性筛分解质因数得到，时间复杂度 $O(n \log \log n)$。（好好线性筛应该能做到线性）
答案即为所有 $f_p \times q$ 之和。注意如果没有 $p=2$ 会多一次。
预处理 $O(n \log \log n)$，每组数据 $\Theta(m)$。