传送门

反演: $$ \begin{aligned} \sum_i F(i)&=\sum_i\sum_{d|i}F(d)[\frac id=1]\\ &=\sum_i\sum_{d|i}F(d)\sum_{p|\frac id}\mu(p)\\ &=\sum_i\sum_{d|i}F(d)\sum_{d|p|i}\mu(\frac pd)\\ &=\sum_p(\sum_{p|i}1)(\sum_{d|p}F(d)\mu(\frac pd))\\ &=\sum_p\lfloor\frac np\rfloor(\sum_{d|p}F(d)\mu(\frac pd)) \end{aligned} $$

把后面那坨东西拿出来:$G(n)=\sum_{d|n}F(d)\mu(\frac nd)$,由于积性函数的狄利克雷卷积仍然是积性函数,我们考虑$G(p^d)$($p$为质数),发现$d=1$时这个东西必定是$0$。

所以,只有每个质因子次数都大于$1$的数才会产生贡献,而些数的个数是$O(\sqrt n)$级别的(证明大概是每个这样的数都能表示成$x^2y^3$的形式,然后拿积分去近似这个复杂度,就是$\int_0^{\sqrt n}{(\frac n{x^2})}^{1/3}=O(\sqrt n)$)。所以把这些数全部搜出来,然后挨个算贡献就行了。

#include <cstdio>
#include <cstring>
#define MAXN 10000010
#define LL long long

LL n;
bool flag[MAXN];
int prime[MAXN],nump;
LL ans=0;
int debug=0;

void init(){
    for(LL i=2;i*i<=n;i++){
        if(!flag[i]) prime[++nump]=i;
        for(int j=1;j<=nump && i*i*prime[j]*prime[j]<=n;j++){
            flag[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

void dfs(int id,LL x,LL f){
    LL p=prime[id];
    LL f1=1,f2=p,f3=p*p;
    if(id>nump || x>n/f3){
        ans+=n/x*f;
        return;
    }
    dfs(id+1,x,f);
    LL d=n/x/f3;
    for(int i=2;d;i++){
        d/=p;
        LL temp=(i%p?f2:f3)-((i-1)%p?f1:f2);
        dfs(id+1,x*f3,f*temp);
        f1=f2; f2=f3;
        f3*=p;
    }
}

int main(){
#ifdef DEBUG
    freopen("148.in","r",stdin);
#endif
    scanf("%lld",&n);
    init();
    dfs(1,1,1);
    printf("%lld\n",ans);
}