题目
Description
给出N，统计满足下面条件的数对(a,b)的个数：
1.1<=a<b<=N
2.a+b整除a×b
Input
一行一个数N
Output
一行一个数表示答案
Sample Input
15
Sample Output
4
HINT
数据规模和约定
Test N Test N
1 <=10 11 <=5×10^7
2 <=50 12 <=10^8
3 <=10^3 13 <=2×10^8
4 <=5×10^3 14 <=3×10^8
5 <=2×10^4 15 <=5×10^8
6 <=2×10^5 16 <=10^9
7 <=2×10^6 17 <=10^9
8 <=10^7 18 <=2^31-1
9 <=2×10^7 19 <=2^31-1
10 <=3×10^7 20 <=2^31-1
题解
题目要求$\sum_{a=1}^{n}\sum_{b=a+1}^{n}[a+b\vert ab]$
这里不得不吐槽一下这个公式实在是太丑了……
设$d=\gcd(a,b),a=xd,b=yd$，则$xd+yd\vert xyd^2$，即$x+y\vert xyd$
注意到$\gcd(x,y)=1$，根据辗转相减法，$\gcd(x+y,y)=\gcd(x,x+y)=\gcd(x,y)=1$，所以$x,y$与$x+y$互质
所以只能是$x+y\vert d$
设$d=t(x+y)$，则$b=yt(x+y)$，所以$n$中$d$的倍数的个数为$\frac{n}{y(x+y)}$，同时产生贡献的$x,y$小于$\sqrt n$
所以上面那个极丑的式子可以化成$\sum_{i=1}^{\sqrt n}\sum_{j=i+1}^{\sqrt n}[\gcd(i,j)==1]\frac{n}{j(i+j)}$
即$\sum_{i=1}^{\sqrt n}\sum_{j=1}^{i-1}[\gcd(i,j)==1]\frac{n}{i(i+j)}$
这个很莫比乌斯啊……
$f(x)=\sum_{i=1}^{\sqrt n}\sum_{j=1}^{i-1}[\gcd(i,j)==x]\frac{n}{i(i+j)},F(x)=\sum_{x\vert d}f(d)=\sum_{x\vert d}\sum_{i=1}^{\sqrt n}\sum_{j=1}^{i-1}[\gcd(i,j)==d]\frac{n}{i(i+j)}$
$F(x)=\sum_{i=1}^{\sqrt n}\sum_{j=1}^{i-1}[x\vert \gcd(i,j)]\frac{n}{i(i+j)}$
$=\sum_{i=1}^{\left\lfloor\frac{\sqrt n}{x}\right\rfloor}\sum_{j=1}^{i-1}\frac{n}{x^2i(i+j)}$
$f(1)=\sum_{d=1}^{\sqrt n}\mu(d)\sum_{i=1}^{\left\lfloor\frac{\sqrt n}{d}\right\rfloor}\sum_{j=1}^{i-1}\frac{n}{d^2i(i+j)}$
然后前面两个求和暴力枚举，最后一个整除分块就能AC……什么玄学的复杂度
注意整除分块的边界条件
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=5e4+5;
int n,tot,m;
LL ans;
int pm[MAX],u[MAX];
bool use[MAX];
void ss(int n)
{
u[1]=1;
for(int i=2;i<=n;++i)
{
if(!use[i]) pm[++tot]=i,u[i]=-1;
for(int j=1;j<=tot&&pm[j]*i<=n;++j)
{
use[pm[j]*i]=1;
if(i%pm[j]==0) break;
u[pm[j]*i]=-u[i];
}
}
}
int main()
{
scanf("%d",&n),ss(m=sqrt(n));
for(int d=1;d<=m;++d)
if(u[d])
{
LL _ans=0;
for(int i=2,_N;i<=m/d;++i)
{
_N=n/d/d/i;
for(int l=1,r,N;l<i&&i+l<=_N;l=r+1)
N=_N/(i+l),r=min(i-1,_N/N-i),_ans+=1ll*(_N/(i+l))*(r-l+1);
}
ans+=u[d]*_ans;
}
return printf("%lld",ans),0;
}
