题目

题目

题解

什么鬼，我竟然用莫比乌斯反演做出来了？！？！？！？！

咳咳，讲讲怎么做吧，设$f$为莫比乌斯函数，那么就有：

$\sum\limits_{k|n}^nk\sum\limits_{i|\frac{n}{k}}^{\frac{n}{k}}\frac{n}{ki}f(i)$

$\sum\limits_{k|n}^n\sum\limits_{i|\frac{n}{k}}^{\frac{n}{k}}\frac{n}{i}f(i)$

设$z=ki$

那么就有

$\sum\limits_{z|n}^n\sum\limits_{i|z}^{z}\frac{n}{i}f(i)$

$\sum\limits_{i|n}^n\frac{n}{i}f(i)\sum\limits_{i|z,z|n}^{n}$

根据$f$的的性质，不难想出我们只需要枚举质因子不重复的$i$，然后对于每个$i$统计$\sum\limits_{i|z,z|n}^{n}$即可。

因为最多$9$个不同的质因子，所以时间复杂度是：$O(2^9+\sqrt{n})$。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> 
#define  N  51000
using  namespace  std;
typedef  long  long  LL;
LL  a[N],b[N],to1;//表示因子
LL  n;
int  v;
void  fenjie(LL  x)//分解质因子
{
    LL  y=sqrt(x);
    for(LL  i=2;i<=y  &&  i<=x;i++)
    {
        if(x%i==0)
        {
            LL  t=0;
            while(x%i==0)x/=i,t++;
            a[++to1]=i;b[to1]=t;
        }
    }
    if(x>1)a[++to1]=x,b[to1]=1;
}
int  main()
{
    scanf("%lld",&n);
    fenjie(n);
    int  limit=(1<<to1)-1;
    LL  ans=0;
    for(int  i=0;i<=limit;i++)
    {
        LL  x=1,y=1;int  z=0;
        for(int  j=1;j<=to1;j++)
        {
            if(i&(1<<(j-1)))
            {
                z++;
                x*=a[j];//有这个数字 
                y*=b[j];//统计 
            }
            else  y*=(b[j]+1);
        }
        LL  f=1;
        if(z&1)f=-1;
        ans+=(n/x)*f*y;//统计个数
    }
    printf("%lld\n",ans);
    return  0;
}