loj509
step1
首先显然有 \(|KX|=\sqrt{a},|YL|=\sqrt{b}\)。
所以延长 \(KX,YL\) ,不难发现：\(|KL|=\sqrt{(\sqrt{a}+\sqrt{b})^2+1^2}\)。
\(S=|KL|^2=(\sqrt{a}+\sqrt{b})^2+1=a+b+1+2\sqrt{ab}\)。
问题转化：求 \(\sum_{i=1}^n\sum_{j=1}^m[i\times j\in 完全平方数]\)。
step2
以下说的 \(i,j\) 都是满足 \(i\times j\) 是完全平方数的 \(i,j\)。
所以，我们发现，如果 \(p|i,p|j，\ \ p\in prime\) 那么 \(i,j\) 的 \(p\) 因子的奇偶性相同。
思路大概明晰了，我们尝试提取 \(i,j\) 的平方因子。
\(i=a\times x,j=b\times y\)。
\(a,b\) 均是完全平方数。
那么 \(x\times y\) 也为完全平方数。
\(x,y\) 剩余了啥？ \(x,y\) 的任意 \(p_i\) 因子就行都相同，此时还只可能为 \(0\ or \ 1\)。
发现 \(x=y\)。
step3
枚举 \(x\) 。
原式可写为 ： \[ \begin{aligned} \sum_{x=1}^{n}[\sqrt{x}\not\in\mathbb{Z}]\sum_{a=1}^{n/x}[\sqrt{a}\in \mathbb{Z}]\sum_{b=1}^{m/x}[\sqrt{b}\in\mathbb{Z}]\\ \sum_{x=1}^{n}[\sqrt{x}\not\in\mathbb{Z}]\lfloor\sqrt{\lfloor\frac{n}{x}\rfloor}\rfloor\lfloor\sqrt{\lfloor\frac{m}{x}\rfloor}\rfloor\\ \sum_{x=1}^{n}\mu(x)^2 \lfloor\sqrt{\lfloor\frac{n}{x}\rfloor}\rfloor\lfloor\sqrt{\lfloor\frac{m}{x}\rfloor}\rfloor \end{aligned} \] 是不是可以 \(\mathcal{O(n)}\) 求了呢？一个大大的 \(n\leq 1.5\times 10^{16}\) 打在你脸上。
step4
发现显然可以整除分块，但是复杂度不是很优，还要求 \(\sum\mu(i)^2\) 。
如何求 \(\sum\mu(i)^2\)
考虑 \(\mu\) 本质是在对于因数个数容斥。
正难则反。我们考虑容斥，我们先 naive 地求出 \(\sum_{p}\sum_{i=1}^{n}[p^2|i,\sqrt{i}\in\mathbb{Z}]\),就是平方因子包括 \(p\) 的数的个数。
形式化地写出： \(\sum_{p}\lfloor\frac{n}{p^2}\rfloor\)
但是此时我们算重了，我们算重的是两个质数积的平方的因数，所以类似的有平方因子包含 \(p_i\cdot p_j\) 的。
形式化写出：\(\sum _{t=p_i\cdot p_j}\lfloor \frac{n}{t^2}\rfloor\)。
利用 \(\mu\) 对因子的容斥。 \[ \sum_{i=1}^n \mu^2(i)\\ =\sum_{i=1}^n\mu(i) \lfloor\frac{n}{i^2}\rfloor\\ =\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\mu(i) \lfloor\frac{n}{i^2}\rfloor\\ \] 此部分复杂度为 \(\mathcal{O(n^\frac{1}{4})}\)。
复杂度为什么对？怎么保证？
发现\(\sqrt{\frac{n}{x}}\) ，当 \(1\leq x\leq n^\frac{1}{3}\) 时取值个数只可能为 \(n^\frac{1}{3}\)。
当 \(n^{\frac{1}{3}}<x\leq n\) 时，取值范围为 \([1,\sqrt{\frac{n}{n^{\frac{1}{3}}}}]=[1,n^{\frac{1}{3}}]\)。
若用 \(t=\sqrt{\frac{n}{x}}\) , 那么 \(x=\frac{n}{t^2}\)。
我们现在用积分算复杂度。
第一部分： \[ \int_{1}^{n^\frac{1}{3}}{x}^{\frac{1}{4}}dx\\ ={x^{\frac{5}{4}}}{\Big|}^{n^{\frac{1}{3}}}_0\\ =n^{\frac{5}{12}} \] 第二部分： \[ \int_{1}^{n^\frac{1}{3}}({\frac{n}{t^2}})^{\frac{1}{4}}dt\\ =n^{\frac{1}{4}}\int_{1}^{n^\frac{1}{3}}x^{-\frac{1}{2}}dt\\ ={n^{\frac{1}{4}}x^{\frac{1}{2}}}\Big|^{n^{\frac{1}{3}}}_0\\ =n^{\frac{1}{4}}\cdot n^{\frac{1}{6}}=n^{\frac{5}{12}} \] 发现这个 \(\mathcal{O(n^\frac{5}{12})}\) 常数不是很优。
可以预处理一部分的 \(\sum\mu(x)^2\) 然后降低常数，（或许可以证明能降低复杂度下界）