自动搬运

查看原文

来自洛谷，原作者为

	星小雨 烟火 咱 烟火

搬运于2025-08-24 22:00:29，当前版本为作者最后更新于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$显然可以使用数论分块。

代码如下：

#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)$的？问号问号。。