[ABC254D] Together Square Solution

更好的阅读体验戳此进入

题面

给定 n,求满足以下条件的二元组 (i,j) 数量:1i,jn,i×j=k2(kN)

Solution

首先有一个较为显然的想法,即埃筛 [1,n] 每个数的所有因数,然后枚举每个 i2,i[1,n],将 i×i 转化为 (i×t)×(it),其中 ti 的因数,然后如果 i×tn 那么若 t=1ansans+1,反之 ansans+2。不过很遗憾这个很简单也很好写的思路是假的,不难发现比如 6×64×9,这里的因数是 32,然后我们忽略了,所以会漏。

考虑正解,有个妙妙转化,即将原式的 i,j 转化为 i=a2×c,j=b2×c,然后我们钦定 i<j,此时计算后对于每个答案都 ×2 可以不漏 i>j 的部分,然后将最后的答案加上 n 即不漏 i=j 的部分。

然后考虑处理钦定 i<j 后的答案,不难想到有 i<j<na2×c<b2×c<na2<b2<nca<b<nc

于是不难发现 a,b 都是 n 级别的,于是枚举 a,b,对于确定的 a,b,则显然有 c[1,nb2],则此时的答案贡献即为 2×nb2。然后发现这个东西还是假的,会重,即对于 gcd(a,b)1c,显然会被 a=agcd(a,b),b=bgcd(a,b) 所包含,所以不难想到只要将对答案的贡献转化为 2×nb2×[gcd(a,b)=1] 即可不重不漏地求出答案。

Code

UPD

update-2022_12_06 初稿