[国家集训队]和与积

$\color{deeppink}link$

给出 $n$，统计满足下面条件的数对 $(a,b)$ 的个数：

1. $1\le a < b \le n$
2. $a+b~\vert ~a\times b$

$\sum_{i,j}[i+j~\vert~ij][1\le i<j\le n]\\ =\sum_{i,j,d,s,t}[d=\gcd(i,j)][i=sd][j=td][1\le sd<td\le n][d(s+t)~\vert~d^2st][s\bot t]$

注意到 $[d(s+t)~\vert~d^2st]$ 可以化为 $[s+t~\vert~dst]$，而 $s\bot t$，故 $s+t \nmid st$，所以可以化为 $[s+t~\vert~d]$。

$=\sum_{s,t,d}[1\le sd<td\le n][s+t~\vert~d][s\bot t]\\ =\sum_{s,t,d,k}[d=k(s+t)][s\bot t][1\le sk(s+t)<tk(s+t)\le n][k\ge 1 ]\\ =\sum_{s,t,k}[s\bot t][k\in[1,\frac{n}{t(s+t)}]][s<t]\\ =\sum_{s,t}\lfloor\frac{n}{t(s+t)} \rfloor[s\bot t][s<t]\\ =\sum_{s,t,k}\lfloor\frac{n}{t(s+t)} \rfloor[k~\vert~s][k~\vert~t][s<t]\mu(k)\\$

换成上下界的形式

$\sum_{t=1}^n\sum_{s=1}^{t-1}\sum_{k~\vert\gcd(s,t)}\lfloor\frac{n}{t(s+t)}\rfloor\mu(k)\\ =\sum_{k=1}^n\mu(k) \sum_{t=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{s=1}^{t-1}\lfloor\frac{n}{k^2t(s+t)}\rfloor$

注意到 $k^2$ 和 $t^2$ 应小于等于 $n$，否则后面的式子变为 $0$。

$=\sum_{k=1}^{\sqrt {n}} \mu(k) \sum_{t=2}^{\frac{\sqrt n}{k}}\sum_{s=t+1}^{2t-1}\lfloor \frac{\lfloor\frac{n}{k^2t}\rfloor}{s} \rfloor$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=sqrt(3e7)+555500;

int n,mu[N],ans,a[N],cnt,pri[N],m;

void init()
{
	m=sqrt(n);mu[1]=1;
	for(int i=2;i<=m;i++)
	{
		if(!a[i])pri[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&pri[j]*i<=m;j++)
		{
			a[i*pri[j]]=1;
			if(i%pri[j]==0)break;
			mu[i*pri[j]]=-mu[i];
		}
	}
}

int find(int x,int L,int R)
{
//	cout<<x<<' '<<L<<' '<<R<<' ';
	int ans=0;R=min(R,x);
	for(int i=L;i<=R;i++)
	{
		int val=x/i,r=min(R,x/val);
		ans+=(r-i+1)*val;
		i=r;
	}
//	cout<<ans<<'\n';
	return ans;
}

main()
{
	cin>>n;init();
	for(int k=1;k<=m;k++)if(mu[k])
	{
//		cout<<k<<' '<<mu[k]<<'\n';
		for(int t=2;t<=m/k;t++)
		{
			ans+=find(n/(k*k*t),t+1,2*t-1)*mu[k];
		}
	}
	cout<<ans;
}