题解 P4844 【LJJ爱数数】

· · 题解

这里详细解说一下出题人说的pjy的方法

可以化简得到：(a+b)c=ab，于是ab-bc-ac+c^2=c^2，所以(a-c)(b-c)=c^2

设a-c=km^2，b-c=kn^2，则c=kmn。

若k>1，(a,b,c)=(km^2+kmn, kn^2+kmn, kmn)≠1(有个公约数k)，矛盾。故k=1

由此我们知道a-c=m^2，b-c=n^2是完全平方数。

因为(a,b,c)=(m(m+n)，n(m+n)，mn)=（(m+n)*(m，n)，mn）=1，所以(m,n)=1

故充要条件为1<=a,b,c<=n，a-c, b-c是完全平方数，c^2=(a-c)(b-c)，(a-c，b-c)=1

上面这段应该好理解

枚举(a-c)，用莫比乌斯反演求出一定范围内与sqrt(a-c)互质的数的个数即可。

为了防止题目输入的n和上面的n混淆，我们在下面定义定义 x = m，y = n

枚举(a-c)

其实是枚举 sqrt(a-c) 即 x

一定范围：

就是求出y的范围

因为 a,b,c <= n

c = xy

所以 y = \frac{c}{x} <= \frac{n}{x}

因为 a-c = x^2

所以 a = c + x^2 <= n

c = xy

所以 x^2 + xy <= n

y <= \frac{n-x^2}{x} b-c = y^2 y^2 + xy = b <= n

利用初三的数学可以知道

-\frac{x}{2} - \sqrt{n + \frac{x^2}{4}} < 0 < y <= -\frac{x}{2} + \sqrt{n + \frac{x^2}{4}}

所以 y <= min(-\frac{x}{2} + \sqrt{n + \frac{x^2}{4}},\frac{n-x^2}{x})

然后是莫比乌斯

答案是 \sum_{x=1}^{\sqrt n} \sum_{y=1}^{s[x]} [gcd(x,y) = 1] //s[x] 是此时x,y的上限

可以将每个

$\sum_{y=1}^{s[x]}[gcd(x,y)=1] $ = $\sum_{y=1}^{s[x]}\sum_{d|x,d|y}u(d) $ //u就当莫比乌斯函数 = $\sum_{d=1,d|x}^{s[x]}u(d)[\frac{m}{d}]

然后暴力枚举 s[x] 约数即可

但是,求出一个数的约数要 \sqrt n 的时间

没关系，预处理出 1～\sqrt n每个数约数 枚举倍数