Matt Blog

题目

莫反好题

题意

$f(x)$ 表示满足 $(a,b,c)\in \Z^3,c\le x,a<b,\gcd(a,b)=1,a^2+b^2=c^2$ 的 $(a,b,c)$ 组数，求 $f(l)...f(r)$。$T\le100,l\le r\le10^9,r-l \le10^5$。

做法

设 $D=\max(r-l)=10^5$。

第一步赛时就没有想到。

$(a,b,c)$ 都能用 $(m^2-n^2,2mn,m^2+n^2)$ 表示，此时只用满足 $m>n,\gcd(m,n)=1,(m\%2)\not= (n\%2)$。

先想如何计算 $f(N)$。

因为要满足 $\gcd(m,n)=1$，套路地使用莫反。

$[\gcd(m,n)=1]=\sum_{d|m,d|n}\mu(d)$

$f(N)=[\gcd(m,n)=1][m^2+n^2\le N][(m\%2)\not=(n\%2)]=\sum_{d|m,d|n}\mu(d)[m^2+n^2\le N][(m\%2)\not=(n\%2)]$

设 $m=dx,n=dy$，即要求 $x^2+y^2\le \frac{N}{d^2}$。

先枚举 $d\in[1,\sqrt N]$，再枚举 $x\in [1,\frac{\sqrt N}d]$，总复杂度为 $\mathcal O(\sqrt N+\frac{\sqrt N}2+\frac{\sqrt N}3+...)=\mathcal O(\sqrt N\ln \sqrt N)$。

直接做就是 $\mathcal O(TD\sqrt r\ln \sqrt r)$，拼上暴力获得 80pts。

不难发现每次单独求 $f(N)$ 过于麻烦，可以先求出 $f(l)$，再对于 $i\in[l+1,r]$ 每次加上满足 $m^2+n^2=i$ 的情况。

实际上直接暴力枚举 $m\in[1,\sqrt r]$ 后，再枚举 $l-m^2\le n^2 \le r-m^2$，即 $\sqrt{l-m^2}\le n\le \sqrt{r-m^2}$。

估一下复杂度

$\because (\sqrt {r-m^2}-\sqrt {l-m^2})(\sqrt {r-m^2}+\sqrt {l-m^2})=r-m^2-l+m^2=r-l\le D \\ \therefore 当 \sqrt {r-m^2}-\sqrt {l-m^2}=\sqrt {r-m^2}+\sqrt {l-m^2} 时,即 l=m^2,r=D-m^2,\max(\sqrt {r-m^2}-\sqrt {l-m^2})=\sqrt {D-2m^2}\le \sqrt D$

所以单次复杂度会比 $O(\sqrt D)$ 更小，计算 $[l+1,r]$ 的部分复杂度为 $O(\sqrt{rD})$。

综上，本题复杂度为 $O(T\sqrt r\ln \sqrt r+T\sqrt{rD} \log \sqrt r)$。

前一半是 $3\times 10^7$ 左右，后面是 $10^{10}$ 左右，由于计算时是往大的算了，而且 gcd 的常数非常小，所以实际远没有这么大，如果真的被卡常了，可以通过预处理 $m$ 的质因子，少一个求 $\gcd$ 的 $\log \sqrt r$。

感觉难点主要在对后半部分暴力可过的观察和复杂度计算。

贴一手代码。