一些 trick
高次整除分块
对 \(\large\lfloor\frac{n}{i^2}\rfloor\) 整除分块，\(\large r=\sqrt{\lfloor\frac{n}{\lfloor\frac{n}{l^2}\rfloor}\rfloor}\).
容易发现对于 \(i\le n^{\frac{1}{3}}\) 和 \(i\ge n^{\frac{1}{3}}\)，都只有 \(n^\frac{1}{3}\) 种取值，所以复杂度 \(O(n^{\frac{1}{3}})\).
对于更高次也是同理的。
\(\mu^2\) 的前缀和计算
详见 P9238 [蓝桥杯 2023 省 A] 翻转硬币.
对 \(i\) 进行唯一分解得 \(\displaystyle i=\prod p_i^{\alpha_i}\).
令 \(\displaystyle P=\prod p_i^{\lfloor\frac{\alpha_i}{2}\rfloor}\)，那么 \(\mu^2(i)=1\Leftrightarrow P=1\).
那么 \(\displaystyle\mu^2(i)=\epsilon(P)=\sum_{d|P}\mu(d)\).
可以得到 \(\displaystyle\mu^2(i)=\sum_{d^2|i}\mu(d)\).
利用高次整除分块，可以对 \(\mu\) 线性筛或杜教筛。
杜教筛预处理 \(n^{\frac{2}{5}}\) 的前缀和可以做到 \(O(n^{\frac{2}{6}})\).
调和数求值
P1943 LocalMaxima
推出来的式子是第 \(n\) 个调和数 \(\displaystyle\sum_{i=1}^{n}\frac{1}{i}\).
有一个性质：
右式是收敛的，\(\gamma\) 称为欧拉常数，近似值 \(0.57721566490153285\).
对于较大的 \(n\) 精度还是不错的。
差分前缀和优化函数求和
P9308 「DTOI-5」#1f1e33
已知函数 \(F\)，求函数 \(G\) 满足
差分有
所以对于 \(d|n\) 才会对 \(\Delta G\) 产生贡献。
这样时间复杂度从 \(O(n\sqrt{n})\) 优化至 \(O(n\log n)\).
完全平方数匹配
判断 \(a\times b\) 为完全平方数有一种简单的方法：
记 \(\displaystyle f(x)=\max_{d^2|x}d\)，\(\displaystyle g(x)=\frac{x}{f^2(x)}\).
\(f^2(x)\) 也可以叫做 \(x\) 的最大平方因子。
那么 \(a\times b\) 为完全平方数即 \(g(a)=g(b)\).
带根号的整除分块
若 \(d^2k\in[l,r]\)，那么 \(\displaystyle d\in[\sqrt{\frac{l}{k}},\sqrt{\frac{r}{k}}]\).
考虑怎么找到 \(\displaystyle\lceil\sqrt{\frac{l}{k}}\rceil\) 和 \(\displaystyle\lfloor\sqrt{\frac{r}{k}}\rfloor\) 相同的一段数。
对于 \(i\)，找到最大的 \(j\) 应该是
好奇怪的渲染。