当 \(n = 1\) 时，\(F(1)\) 显然为 \(1\) 。
另一种推导 \(F\) 的方式是莫比乌斯反演：
\[\begin{aligned}F(n) & = \sum\limits_{i = 1} ^ n i[\gcd(i, n) = 1] \\& = \sum\limits_{i = 1} ^ n i \sum\limits_{d \mid \gcd(i, n)} \mu(d) \\& = \sum\limits_{d\mid n} \mu(d) \sum\limits_{i = 1} ^ n i[i\mid d] \\& = \sum\limits_{d\mid n} \mu(d) d \frac{\frac n d (\frac n d + 1)}{2} \\& = \frac n 2 \sum\limits_{d\mid n} \mu(d) \left(\frac n d + 1\right) \\& = \frac {n(\varphi(n) + \epsilon(n))} 2\end{aligned}\]最后一步是因为 \(\mu * \mathrm{id} = \varphi\)，\(\mu * 1 = \epsilon\) 。
答案为 \(n\sum\limits_{d\mid n} F(d)\)，化简为 \(\dfrac n 2 \left(1 + \sum\limits_{d\mid n} d \varphi(d)\right)\) 。线性筛出 \(1 * (\mathrm{id} \times \varphi)\) 即可做到 \(\mathcal{O}(T + n)\) 。代码 。
III. P4318 完全平方数设 \(f(n)\) 表示 \([1, n]\) 当中非完全平方数倍数的数的个数 。二分答案，找到最小的 \(r\) 使得 \(f(r) \geq K\)，则 \(r\) 即为所求 。
首先去掉 \(4, 9, \cdots, p ^ 2\) 的倍数，但同时是其中两个数的倍数的数会被算两次，所以加上 \((p_1p_2) ^ 2\) 的倍数，依次类推 。相当于对 \(\mathbb N\) 做容斥 ， 自然想到莫比乌斯函数 。因此
\[f(n) = \sum\limits_{i} \mu(i) \left\lfloor\dfrac n {i ^ 2} \right\rfloor\]直接计算 ， 时间复杂度 \(\mathcal{O}(\sqrt n \log n)\) 。代码 。
IV. P2257 YY 的 GCD\[\begin{aligned}\mathrm{answer} & = \sum_{i = 1} ^ n \sum_{j = 1} ^ m [\gcd(i, j)\in \mathbb P] \\& = \sum_{p\in \mathbb P} \sum_{i = 1} ^ {\frac n p} \sum_{i = 1} ^ {\frac m p}[\gcd(i, j) = 1] \\& = \sum_{p\in \mathbb P} \sum_{d = 1} ^ {\min(\frac np, \frac mp)} \mu(d) \dfrac {n}{pd} \dfrac{m}{pd}\end{aligned}\]注意到分母上的 \(pd\) 与两个变量相关，很麻烦 。不妨设 \(T = pd\)，得
\[\sum_{T = 1} ^ {\min(n, m)} \sum_{p\mid T\land p\in\mathbb P} ^ T \dfrac n T \dfrac m T \mu \left(\dfrac T p\right)\]这一步调整了计算顺序使得可通过乘法分配律提出向下取整的式子 。
另一种推导方式：考虑对 \([\gcd(i, j) = p]\) 容斥，然后对所有质数 \(p\) 求和，可知贡献系数 \(f\) 为所有容斥系数之和，即 \(f = \sum\limits_{p\in \mathbb P} \mu * \epsilon_p(n)\) 。换句话说，\(f\) 等于将 \(\mu\) 的 下标 扩大质数倍后求和 。我们发现 \(f(T) = \sum\limits_{p \mid T\land p\in \mathbb P} \mu\left(\dfrac T p\right)\)，与上式等价 。
\(f\) 可以类似埃氏筛 \(n\log\log n\) 求出，因为每个位置仅与其所有质因子有关 。将 \(f\) 前缀和后整除分块即可 。时间复杂度 \(\mathcal{O}(T\sqrt n + n \log\log n)\) 。
尽管 \(f\) 不是积性函数，但 \(f(T)\) 可以线性筛 。具体方式留给读者自行推导，时间复杂度 \(\mathcal{O}(T\sqrt n+n)\) 。代码 。
V. P3455 [POI2007] ZAP-QueriesP2522 的子问题 ， 代码 。
VI. P2568 GCDP2257 的子问题 。
VII. P1829 [国家集训队] Crash 的数字表格设 \(c = \min(n, m)\) 。
根据 \(ij = \gcd(i, j) \times \mathrm{lcm}(i, j)\) 枚举 \(d = \gcd(i, j)\)，得
\[\begin{aligned}& \sum\limits_{d = 1} ^ c \frac 1 d \sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m ij[\gcd(i, j) = d] \\& \sum\limits_{d = 1} ^ c d \sum\limits_{i = 1} ^ {\frac n d} \sum\limits_{j = 1} ^ {\frac m d} ij [i\perp j]\end{aligned}\]莫比乌斯反演，得
\[\begin{aligned}& \sum\limits_{d = 1} ^ c d \sum\limits_{e = 1} ^ {\frac c d} \mu(e) \sum\limits_{i = 1} ^ {\frac n d} \sum\limits_{j = 1} ^ {\frac m d} ij [e\mid i \land e\mid j] \\& \sum\limits_{d = 1} ^ c d \sum\limits_{e = 1} ^ {\frac c d} \mu(e) e ^ 2 \sum\limits_{i = 1} ^ {\frac n {de}} \sum\limits_{j = 1} ^ {\frac m {de}} ij \\\end{aligned}\]注意到后面两个和式不太好化简 ， 我们设 \(S(T) = \sum\limits_{i = 1} ^ {\frac n T}\sum\limits_{j = 1} ^ \frac m T ij\)，并令 \(T = de\) ， 交换枚举顺序，得
\[\begin{aligned}& \sum\limits_{T = 1} ^ c S(T) \sum\limits_{e \mid T} \mu(e) e ^ 2 \frac T e \\& \sum\limits_{T = 1} ^ c S(T) T \sum\limits_{e \mid T} \mu(e) e \\\end{aligned}\]至此已经可以狄利克雷前缀和 \(c\log \log c\) 求解问题 。但注意到 \(\mu \cdot \mathrm{id}\) 是积性函数，所以 \(f = 1 * (\mu \cdot \mathrm{id})\) 也是积性函数，且其在质数幂处的取值可快速计算，可线性筛 。则答案式化简为 \(\sum\limits_{i = 1} ^ c S(i)f(i)i\)，其中仅 \(S\) 与 \(n, m\) 有关 。同时注意到 \(S\) 仅涉及到 \(n, m\) 整除值处的等差数列求和，因此求出 \(f(i) i\) 的前缀和后，可整除分块 \(\mathrm{O}(\sqrt c)\) 求解答案 。
时间复杂度 \(\mathcal{O}(c + T\sqrt c)\) 。代码 。
VIII. AT5200 [AGC038C] LCMs令 \(S = \sum\limits_{i = 1} ^ N \sum\limits_{j = 1} ^ N \mathrm{lcm}(A_i, A_j)\)，则答案为 \(S\) 减去 \(A\) 的和之后除以 \(2\) 。问题转化为求 \(S\) 。
推荐阅读
- 前端程序员学习 Golang gin 框架实战笔记之一开始玩 gin
- 1 Libgdx游戏学习——环境配置及demo运行
- 苹果ipad分屏功能怎么使用（ipad 9可以分屏学习吗)
- Go设计模式学习准备——下载bilibili合集视频
- 学习ASP.NET Core Blazor编程系列五——列表页面
- 七 Netty 学习：NioEventLoop 对应线程的创建和启动源码说明
- ZCTF note3：一种新解法
- 学习ASP.NET Core Blazor编程系列四——迁移
- 五 Netty 学习：服务端启动核心流程源码说明
- 【前端必会】走进webpack生命周期，另类的学习方法