OI - LJJ爱数数(洛谷)

……

---

# 题面

> Linked 洛谷 P4844

点击展开/折叠 题面

给定 $N$（$N\le10^{12}$），求

$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N[\gcd(i,j,k)=1][\tfrac 1i+\tfrac 1j=\tfrac 1k]$$

---

# 解析

看到奇怪的条件 $\tfrac 1a+\tfrac 1b=\tfrac 1c$（像极了并联电阻），考虑转化一下：

$$\Leftrightarrow bc+ac=ab\Leftrightarrow ab+c^2-bc-ac=c^2\Leftrightarrow (b-c)(a-c)=c^2$$

我们发现 $\gcd(a,b,c)=\gcd(a-c,b-c,c)$，令 $x=a-c,y=b-c$，也就是说

$$\gcd(a,b,c)=1\Leftrightarrow\gcd(x,y,c)=1$$

显然 $c^2$ 是完全平方数，$c^2$ 质因数分解后，相同的质因子一定有偶数个，要使 $\gcd(x,y,c)=1$，则 $c^2$ 的相同的质因子要么分给 $x$ 要么分给 $y$，于是 $\gcd(x,y)=1$，即

$$\gcd(a,b,c)=1\Leftrightarrow\gcd(x,y,c)=1\Leftrightarrow\gcd(x,y)=1$$

根据之前的分析，$c^2$ 的每个平方因子要么分给 $x$ 要么分给 $y$，则 $x,y$ 都是完全平方数，则有

$$\gcd(x,y)=1\Leftrightarrow\gcd(\sqrt x,\sqrt y)=1$$

令 $p=\sqrt x,q=\sqrt y$，这样就把 $a,b,c$ 三个元降为 $p,q$ 两个元了~

注意到 $p,q\le \sqrt n$，而 $a,b\le n$ 则 $\max\{p^2,q^2\}+pq\le n$。

这样再来反演，枚举的时候使 $p< q$，最后答案乘二加一即可：

$$\begin{aligned} &\sum_{a=1}^n\sum_{b=1}^n\sum_{c=1}^n[\gcd(a,b,c)=1][\tfrac 1a+\tfrac 1b=\tfrac 1c]\\ =&\sum_{p=1}^{\sqrt n}\sum_{q=p+1}^{\sqrt n}[gcd(p,q)=1][q^2+pq\le n]\\ =&\sum_{d=1}^{\sqrt n}\mu(d)\sum_{p=1,d\mid p}^{\sqrt n}\sum_{q=p+1,d\mid q}^{\sqrt n}[q^2+pq\le n]\\ =&\sum_{d=1}^{\sqrt n}\mu(d)\sum_{q=1,d\mid q}^{\sqrt n}\sum_{p=1,d\mid p}^{q-1}[q^2+pq\le n] \end{aligned}$$

考虑对 $p$ 的取值范围解方程，可得

$$\begin{cases}p< q\\q^2+pq\le n\end{cases}\Rightarrow p\le\min\{q-1,\tfrac{n-q^2}{q}\}$$

于是答案又可以写为：

$$\sum_{d=1}^{\sqrt n}\mu(d)\sum_{q=1,d\mid q}^{\sqrt n}\left\lfloor\frac{\min\{q-1,\tfrac{n-q^2}{q}\}}{d}\right\rfloor$$

至此可以在低于 $O(\sqrt n\log\sqrt{n})$ 的复杂度内解决本问题。（$\log\sqrt n$ 是调和级数）

---

# 源代码

/*Lucky_Glass*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;

const int N=1e6+10;

ll n;
int nprm,mu[N],prm[N/10];
bool vis[N];

void Init(){
	mu[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i]) mu[prm[++nprm]=i]=-1;
		for(int j=1;j<=nprm && prm[j]*i<N;j++){
			vis[prm[j]*i]=true;
			if(i%prm[j]==0) break;
			mu[prm[j]*i]=-mu[i];
		}
	}
}
inline int Calc(int i){return (int)min(i-1ll,(n/i)-i);}
int main(){
	Init();
	scanf("%lld",&n);
	int sqn=sqrt(n);
	long long ans=0;
	for(int i=1;i<=sqn;i++)
		for(int j=i;j<=sqn;j+=i)
			ans+=mu[i]*(Calc(j)/i);
	printf("%lld\n",ans<<1|1);
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &无法传达到的悲伤\\ &藏在我的笑容下\ 听得见吗\\ &把你刻在我的城墙\\ &把所有记忆\ 全部埋藏\ ”\\ ——&\text{《404 Not Found》By 赤羽} \end{split}$$

> Linked 404 Not Found-Bilibili