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)\)。
D LCM
洛谷原题 P1829 [国家集训队] Crash的数字表格 / JZPTAB。
标签：Contest5408,lfloor,函数,limits,数论,sum,rfloor,log,gcd From： https://www.cnblogs.com/AugustLight/p/18328863