「题解」「国家集训队互测 2012」和与积

中国国家集训队互测 2012，by ayq，一道 数论 题。

题目链接：Luogu P4466。

题目

一句话题意。

给定 \(n(n\leq 2^{31}-1)\)，求满足

1. \[1\leq a<b\leq n\]
2. \[(a+b)\mid ab\]

的数对 \((a,b)\) 的个数。

题解

思路

第一个条件没得说，主要从第二个条件 \((a+b)\mid(a\times b)\) 入手。

考虑恒等式 \(\gcd(a,b)=\gcd(a-b,b)\)，我们不难发现
\[\gcd(a,b)=\gcd(a+b,a)\]

进一步地，我们有
\[
\begin{aligned}
&\gcd(a,b)=1\\
\Rightarrow&\gcd(a+b,a)=\gcd(a+b,b)=1\\
\Rightarrow&(a+b)\nmid ab
\end{aligned}
\]

不妨设 \(d=\gcd(a,b),a=id,b=jd\)，那么我们有
\[
(id+jd)\mid ijd^2 \Rightarrow (i+j)\mid ijd
\]

又 \(\gcd(i,j)=1\Rightarrow (i+j)\nmid ij\)，所以有
\[(i+j)\mid d\]

经过上面的推理，我们不难写出答案的表达式
\[
\texttt{ans}=\sum _ d\sum^{\left\lfloor\frac{n}{d}\right\rfloor} _ {i=1}\sum^{i-1} _ {j=1}\left[(i+j)\mid d][\gcd(i,j)=1\right]
\]

改变求和顺序
\[
\texttt{ans}=\sum^n _ {i=1}\sum^{i-1} _ {j=1}\left[\gcd(i,j)=1\right]\sum _ d\left[(i+j)\mid d\right]
\]

显然 \(d\in [1,\left\lfloor\frac{n}{i}\right\rfloor]\)，所以我们有
\[\left(\sum _ d[(i+j)\mid d]\right)\Rightarrow \left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{i+j}\right\rfloor\]
\[
\texttt{ans}=\sum^n _ {i=1}\sum^{i-1} _ {j=1}[\gcd(i,j)=1]\left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{i+j}\right\rfloor
\]

先开一下括号
\[
\texttt{ans}=\sum^n _ {i=1}\sum^{i-1} _ {j=1}[\gcd(i,j)=1]\left\lfloor\frac{n}{i(i+j)}\right\rfloor
\]

观察到当 \(i>\sqrt{n}\) 时 \(\left\lfloor\frac{n}{i(i+j)}\right\rfloor=0\)，我们可以缩小 \(i\) 的范围。
\[
\texttt{ans}=\sum^\sqrt{n} _ {i=1}\sum^{i-1} _ {j=1}\left\lfloor\frac{n}{i(i+j)}\right\rfloor[\gcd(i,j)=1]
\]

考虑到 \(\texttt{Dirichlet}\) 卷积中 \((\mu\ast 1)(x)=\epsilon(x)\)，即莫比乌斯反演。

所以我们可以进一步化简答案。
\[
\texttt{ans}=\sum^\sqrt{n} _ {i=1}\sum^{i-1} _ {j=1}\left\lfloor\frac{n}{i(i+j)}\right\rfloor\sum _ {k\mid\gcd(i,j)}\mu(k)
\]

设 \(i=xk,j=yk\)，交换求和顺序，有
\[
\texttt{ans}=\sum^\sqrt{n} _ {k=1}\mu(k)\sum^{\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor} _ {i=1}\sum^{i-1} _ {j=1}\left\lfloor\frac{n}{xk(xk+yk)}\right\rfloor
\]

最后化简为
\[
\texttt{ans}=\sum^\sqrt{n} _ {k=1}\mu(k)\sum^{\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor} _ {i=1}\sum^{i-1} _ {j=1}\left\lfloor\frac{\left\lfloor\frac{n}{xk^2}\right\rfloor}{x+y}\right\rfloor
\]

最后分析时间复杂度，发现 \(\zeta(1.5)\in\left[2.6,2.7\right]\)，所以时间复杂度为 \(\Theta(n^{\frac{3}{4}})\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int MAXSIZE=1e5+5;

bitset<MAXSIZE> vis;
int tot,prime[MAXSIZE];
int mu[MAXSIZE];

inline void Init(reg int n){
	mu[1]=1;
	for(reg int i=2;i<=n;++i){
		if(!vis[i]){
			mu[i]=-1;
			prime[++tot]=i;
		}
		for(reg int j=1;j<=tot&&i*prime[j]<=n;++j){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0)
				break;
			mu[i*prime[j]]=-mu[i];
		}
	}
	return;
}

inline ll calc(reg int x,reg int y){
	reg ll res=0;
	reg int z=x<<1;
	if(!y)
		return 0;
	for(reg int i=x+1;i<z;i=x+1){
		if(!(y/i))
			return res;
		x=min(y/(y/i),z-1);
		res+=(x-i+1)*(y/i);
	}
	return res;
}

int n;

int main(void){
	Init(1e5);
	scanf("%d",&n);
	reg int m=sqrt(n);
	reg ll ans=0;
	for(reg int i=1;i<=m;++i){
		if(!mu[i])
			continue;
		reg ll sum=0;
		for(reg int j=1;j*i<=m;++j)
			sum+=calc(j,n/(i*i*j));
		ans+=sum*mu[i];
	}
	printf("%lld\n",ans);
	return 0;
}