题解 P4466 【[国家集训队]和与积】
星小雨
2019-01-21 23:37:24
前置知识：莫比乌斯反演
算是一道相对基础的反演题了吧。。
求有多少组$a,b$，满足$1 \le a<b \le n$且$(a+b)|ab$
由于$n \le 10^9 $，反演看起来势在必行
首先是一个很显然的结论：若$(a,b)=1$，则$(a+b) \nmid ab$
为什么呢？因为此时$(a+b,a)=(a+b,b)=1$
所以$(a,b) \ne 1$
所以我们可以设$d=(a,b),a=di,b=dj$，则$(i+j)|ijd$
因为$(i,j)=1$，由上述推论可得$(i+j) \nmid ij$
所以这道题也就是求$(i+j)|d$，$(i,j)=1$且$id,jd \le n$的$(i,j,d)$的数目。
推推式子吧：
$ ans =\sum _{i=1}^n \sum _{j=1}^{i-1} \lfloor \frac {\lfloor \frac{n}{i} \rfloor }{i+j} \rfloor [(i,j) = 1] $
$=\sum_{i=1}^{n}\sum_{j=1}^{i-1} \lfloor \frac {n}{i(i+j) } \rfloor [(i,j)=1]$
$i$最多取到$\sqrt n$，不然后面的$\lfloor \frac {n}{i(i+j) } \rfloor$就等于0了，所以
$ ans=\sum_{i=1}^{\sqrt n}\sum_{j=1}^{i-1} \lfloor \frac {n}{i(i+j) } \rfloor [(i,j)=1]$
套一个莫比乌斯函数的基本操作$[x=1] = \sum_{d|x} \mu (d)$，得：
$ ans= \sum_{i=1}^{\sqrt n}\sum_{j=1}^{i-1} \lfloor \frac {n}{i(i+j) } \rfloor \sum_{k|(i,j)} \mu(k) $
设$i=xk,j=yk$，则：
$ ans = \sum_{k=1}^{\sqrt n} \mu(k) \sum_{x=1}^{\lfloor \frac{\sqrt{n}}{k} \rfloor} \sum_{y=1}^{x-1} \lfloor \frac {n}{xk(xk+yk) } \rfloor $
$ =\sum_{k=1}^{\sqrt n} \mu(k) \sum_{x=1}^{\lfloor \frac{\sqrt{n}}{k} \rfloor} \sum_{y=1}^{x-1} \lfloor \frac {\lfloor \frac{n}{xk^2} \rfloor }{x+y} \rfloor$
枚举了$k,x$之后，$\frac{n}{xk^2}$是固定值，而它除以$x+y$显然可以使用数论分块。
代码如下：
```cpp
#include<cmath>
#include<cstdio>
#include<algorithm>
typedef long long ll;
const int N=1e5+5;
bool b[N];
int p[N],u[N];
ll calc(int x,int y){
ll a=0;int z=x<<1;
if(!y) return 0;
for(int i=x+1;i<z;i=x+1){
if(!(y/i)) return a;
x=std::min(y/(y/i),z-1);
a+=(x-i+1)*(y/i);
}
return a;
}
int main(){
int t=0,n,m,x;ll a=0;
scanf("%d",&n);
m=sqrt(n);
u[1]=1;
for(int i=2;i<=m;++i){
if(!b[i]) p[++t]=i,u[i]=-1;
for(int j=1;j<=t && (x=i*p[j])<=m;++j){
b[x]=1,u[x]=-u[i];
if(!(i%p[j])){u[x]=0;break;}
}
}
for(int i=1;i<=m;++i){
if(!u[i]) continue;
for(int j=1;j*i<=m;++j)
a+=u[i]*calc(j,n/(i*i*j));
}
printf("%lld\n",a);
return 0;
}
```
时间复杂度我感觉是最多 $ O( n^{\frac{3}{4}} \text{ln} \sqrt n) $的吧。。
不过洛咕上有大神证出了是 $O( \sqrt n \text log n)$的？问号问号。。