高次整除分块
对 \(\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\) 的前缀和计算
对 \(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)\).
\[\sum_{i=1}^{n}\mu^2(i)=\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac{n}{i^2}\rfloor \]利用高次整除分块，可以对 \(\mu\) 线性筛或杜教筛。
杜教筛预处理 \(n^{\frac{2}{5}}\) 的前缀和可以做到 \(O(n^{\frac{2}{6}})\).
调和数求值
推出来的式子是第 \(n\) 个调和数 \(\displaystyle\sum_{i=1}^{n}\frac{1}{i}\).
有一个性质：
\[\gamma=\lim_{n\rightarrow\infty}(\sum_{i=1}^{n}\frac{1}{i}-\ln n) \]右式是收敛的，\(\gamma\) 称为欧拉常数，近似值 \(0.57721566490153285\).
对于较大的 \(n\) 精度还是不错的。
差分前缀和优化函数求和
已知函数 \(F\)，求函数 \(G\) 满足
\[G(n)=\sum_{d=1}^{n}dF(\lfloor\frac{n}{d}\rfloor) \]差分有
\[G(n)-G(n-1) \]\[=\sum_{d=1}^{n}d\big(F(\lfloor\frac{n}{d}\rfloor)-F(\lfloor\frac{n-1}{d}\rfloor)\big) \]所以对于 \(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\) 应该是
\[\LARGE\lfloor\min\Bigg(\frac{l-1}{(\lceil\sqrt{\frac{l}{i}}\rceil-1)^2},\frac{r}{\lfloor\sqrt{\frac{r}{i}}\rfloor^2}\Bigg)\rfloor \]好奇怪的渲染。
标签：lfloor,mu,frac,rfloor,trick,sqrt,一些,displaystyle From： https://www.cnblogs.com/SError0819/p/17609926.html