自动搬运

查看原文

来自洛谷，原作者为

	Ynoi 是树剖姐姐喵~

搬运于2025-08-24 22:04:31，当前版本为作者最后更新于2019-02-19 15:46:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

设a-c=k$m^2$，b-c=k$n^2$，则c=kmn。

若k>1，(a,b,c)=(k$m^2$+kmn, k$n^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]$单独取出（x暴力枚举)

$\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$每个数约数 枚举倍数