题解 P4466 【[国家集训队]和与积】

· · 题解

前置知识：莫比乌斯反演

算是一道相对基础的反演题了吧。。

求有多少组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] $ 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)的？问号问号。。