Hillan and the girl
题意
对于1<=n,m<=1e7，T<=1e4，求：
$$
\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j)),其中f(x)=1，当且仅当x为平方数
$$
思路
来，让我们来反演一波：
$$
\sum_{d=1}^{mim(n,m)}f(d)\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]
$$
$$
\sum_{d=1}^{min(n,m)}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)==1]
$$
$$
\sum_{d=1}^{min(n,m)}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t|gcd(i,j)}μ(t)
$$
$$
\sum_{d=1}^{min(n,m)}f(d)\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dt}\rfloor}\sum_{t=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}μ(t)
$$
$$
\sum_{d=1}^{min(n,m)}f(d)\sum_{t=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}μ(t){\lfloor\frac{n}{dt}\rfloor}{\lfloor\frac{m}{dt}\rfloor}
$$
令dt=T，则：
$$
\sum_{T=1}^{min(n,m)}{\lfloor\frac{n}{T}\rfloor}{\lfloor\frac{m}{T}\rfloor\sum_{d|T}f(d)}μ(\frac{T}{d})
$$
由于$d=x^2$
$$
\sum_{T=1}^{min(n,m)}{\lfloor\frac{n}{T}\rfloor}{\lfloor\frac{m}{T}\rfloor\sum_{x=1}^{min(\sqrt{n},\sqrt{m})}\sum_{x^2|T}}μ(\frac{T}{x^2})
$$
对于T的前半部分，我们可以用分块，复杂度为$\sqrt{n}$，对于后半部分，就可以预处理出来。
枚举x，以及每一个$x^2$的倍数$k·x^2$，处理出每一个T的对应的值，然后再求前缀和。
预处理部分的复杂度为O(n)，求的时候的复杂度为$O(T\sqrt{n})$。
看！代码
1 |
|