题意：询问满足$1\leq x\leq n,1\leq y\leq m$且$x,y$均无平方因子的有序对$(x,y)$的$[x,y]$之和，多组数据

以下假设$n\leq m$，设$S(n)=\frac{n(n+1)}2$，$r(n)$表示$n$的最大无平方因子

$\begin{align*}\sum\limits_{i=1}^n\sum\limits_{j=1}^m\mu^2\left((i,j)\right)[i,j]&=\sum\limits_{d=1}^nd\mu^2(d)\sum\limits_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac md\right\rfloor}[i,j][(i,j)=1]\\&=\sum\limits_{d=1}^nd\mu^2(d)\sum\limits_{e=1}^{\left\lfloor\frac nd\right\rfloor}e\mu(e)\sum\limits_{i=1}^{\left\lfloor\frac n{de}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac m{de}\right\rfloor}[i,j]\\&=\sum\limits_{T=1}^nT\sum\limits_{d|T}\mu^2(d)\mu\left(\frac Td\right)\sum\limits_{i=1}^{\left\lfloor\frac nT\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac mT\right\rfloor}[i,j]\end{align*}$

暂停一下，先化一下其中的一部分式子

1.$G(n)=\sum\limits_{d|n}\mu^2(d)\mu\left(\frac nd\right)$

设$n=a^2b$，其中$\mu(b)\ne0$，那么仅当$d=ac$且$(a,c)=1$时$\mu^2(d)\mu\left(\frac nd\right)\ne0$（若$a\nmid d$则$\frac nd$含来自$a$的平方因子，若$(a,c)\ne1$则$d$含平方因子），此时$G(n)=\sum\limits_{c|b}\mu\left(\frac{a^2b}{ac}\right)=\mu(a)\sum\limits_{c|b}\mu\left(\frac bc\right)=\mu(a)[b=1]$，这说明当$n$为完全平方数时，$G(n)=\mu\left(\sqrt n\right)$，否则$G(n)=0$

2.$F(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[i,j]$

直接把jzptab的式子搬过来，$F(n,m)=\sum\limits_{T=1}^nTS\left(\left\lfloor\frac nT\right\rfloor\right)S\left(\left\lfloor\frac mT\right\rfloor\right)\sum\limits_{e|T}e\mu(e)$

这里我们每次求答案都要求很多次$F$，所以还要继续推下去

$Q(n)=\sum\limits_{e|n}e\mu(e)$

首先显然$Q(n)=Q(r(n))$，因为$n$的平方因子对答案没有贡献，接下来考虑$n=r(n)$的情况，设$n=\prod\limits_{i=1}^kp_i$

当$n$为质数时$Q(n)=1-n$，因为$Q$是个积性函数，所以$Q(n)=\prod\limits_{i=1}^k(1-p_i)=(-1)^k\varphi(n)=\mu(n)\varphi(n)$，即是说对于一般的$n$有$Q(n)=\mu(r(n))\varphi(r(n))$

把以上两个结果代入到开始时的式子中，得到$\sum\limits_{p=1}^{\left\lfloor\sqrt n\right\rfloor}p^2\mu(p)\sum\limits_{q=1}^{\left\lfloor\frac n{p^2}\right\rfloor}qQ(q)S\left(\left\lfloor\frac n{p^2q}\right\rfloor\right)S\left(\left\lfloor\frac m{p^2q}\right\rfloor\right)$

枚举$T=p^2q$，得到$\sum\limits_{T=1}^nTS\left(\left\lfloor\frac nT\right\rfloor\right)S\left(\left\lfloor\frac mT\right\rfloor\right)\sum\limits_{p^2|T}\mu(p)Q\left(\frac T{p^2}\right)$

我们要预处理$D(n)=\sum\limits_{p^2|n}\mu(p)Q\left(\frac n{p^2}\right)$，这个直接枚举$p$去更新$p^2$的倍数即可，时间复杂度为$O\left(n\sum\limits_{i=1}^{\left\lfloor\sqrt n\right\rfloor}\frac1{i^2}\right)=O(n)$

总时间复杂度$O\left(n+T\sqrt n\right)$，这题还是挺棒的==

一个小小的trick：我们可以算出答案的$4$倍$\bmod2^{32}$的值，最后$\div4$即可，这样在求$S(n)$的时候不用$\div2$而且可以全程unsigned

#include
     
      typedef unsigned uint;const int T=4000010;int min(int a,int b){return a
      
       m)swap(n,m);		printf("%u\n",solve(n,m)>>2);	}}