VI.LJJ爱数数

题目给出要求这样的东西

\(\dfrac{1}{a}+\dfrac{1}{b}=\dfrac{1}{c}\)

开始胡搞

\(\begin{aligned}\dfrac{1}{a}+\dfrac{1}{b}&=\dfrac{1}{c}\\\dfrac{a+b}{ab}&=\dfrac{1}{c}\\\dfrac{ab}{a+b}&=c\\(a+b)c&=ab\\ac+bc&=ab\\c^2+ac+bc&=ab+c^2\\c^2&=ab+c^2-ac-bc\\c^2&=(a-c)(b-c)\end{aligned}\)

设\((a-c)=x,(b-c)=y\)。如果\(\gcd(a,b,c)> 1\)的话，则一定满足\(\gcd(a,b,c)|a,\gcd(a,b,c)|b,\gcd(a,b,c)|c\)，则又有\(\gcd(a,b,c)|(a-c),\gcd(a,b,c)|(b-c)\)，最终有\(\gcd(x,y)>1\)。反之亦然。

这样，只要保证\(\gcd(x,y)=1\)即可。

这样的话，如果将\(c^2\)的全部质因子分配给\(a-c\)和\(b-c\)的话，相同的质因子必然全部分给了一个数，不然必有\(\gcd(x,y)>1\)。

因此，必有\(x,y\)为完全平方数。

我们就设\(i=\sqrt{x},j=\sqrt{y}\)。则有\(c=ij\)。

因为有\(n\)这个限制，我们必有\(\max(a,b)\leq n\)，不妨设\(a\geq b\)，则必有\(x\geq y,i\geq j\)。

如果我们枚举\(i\)的话，\(j\)就可以是所有满足\(c\leq n,j\leq i\)，且\(\gcd(i,j)=1\)的值。

我们看\(j\)最多可以在什么范围内取。必有\(x+c\leq n\)，即\(i^2+ij\leq n\)，即\(j\leq \dfrac{n}{i}-i\)。

同时，为了避免重复计算，我们还有限制\(j<i\)。

这样的话，\(j\)的上限就是\(\min(\dfrac{n}{i}-i,i-1)\)。设为\(b_i\)。

则我们要求\(\sum\limits_{i=1}^{\sqrt{n}}\sum\limits_{j=1}^{b_i}[\gcd(i,j)=1]\)

老套路了吧。不过注意，这回\(j\)的上限\(b_i\)与\(i\)有关，因此不能直接把它变成下取整的形式，必须保留这个东西。

\(\sum\limits_{i=1}^{\sqrt{n}}\sum\limits_{j=1}^{b_i}[\gcd(i,j)=1]=\sum\limits_{i=1}^{\sqrt{n}}\sum\limits_{j=1}^{b_i}\sum\limits_{x|i,x|j}\mu(x)=\sum\limits_{x=1}^{\sqrt{n}}\mu(x)\sum\limits_{x|i}\left\lfloor\dfrac{b_i}{x}\right\rfloor\)

直接没有任何技术含量地暴力即可。复杂度为\(\sum_{i=1}^{\sqrt{n}}(\dfrac{\sqrt{n}}{i})=\sqrt{n}\log n\)

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6;
int n,mu[N+5],pri[N+5],ans;
void init(){
	mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!pri[i])pri[++pri[0]]=i,mu[i]=-1;
		for(int j=1;j<=pri[0]&&i*pri[j]<=N;j++){
			pri[i*pri[j]]=true;
			if(!(i%pri[j]))break;
			mu[i*pri[j]]=-mu[i];
		}
	}
}
signed main(){
	scanf("%lld",&n),init();
	for(int i=1;i*i<=n;i++)if(mu[i])for(int j=i;j*j<=n;j+=i)ans+=mu[i]*((min(j-1,(n/j)-j))/i);
	printf("%lld\n",ans*2+1);
	return 0;
}