P3911 最小公倍数之和 莫比乌斯反演

题意:

戳这里

分析：

• 推柿子

  我们记 (m) 为值域大小, (c_x) 为 (x) 的个数

[sum_{i=1}^nsum_{j=1}^nlcm(A_i,A_j) \ =sum_{i=1}^msum_{j=1}^m lcm(i,j) imes c_i imes c_j \ =sum_{i=1}^msum_{j=1}^m frac{i imes j imes c_i imes c_j}{gcd(i,j)} \ =sum_{d=1}^msum_{i=1}^{lfloorfrac{m}{d} floor}sum_{j=1}^{lfloorfrac{m}{d} floor}[gcd(i,j)==1]d imes i imes j imes c_{id} imes c_{jd} \ =sum_{d=1}^msum_{i=1}^{lfloorfrac{m}{d} floor}sum_{j=1}^{lfloorfrac{m}{d} floor}sum_{k|gcd(i,j)}mu(k) imes d imes i imes j imes c_{id} imes c_{jd} \ =sum_{d=1}^msum_{k=1}^{lfloorfrac{m}{d} floor} mu(k)sum_{i=1}^{lfloorfrac{m}{dk} floor}sum_{j=1}^{lfloorfrac{n}{dk} floor}d imes i imes j imes k^2 imes c_{idk} imes c_{jdk} \ 然后我们枚举 t=dk 继续推柿子 \ =sum_{t=1}^m tsum_{k|t}mu(k) imes k imes (sum_{i=1}^{lfloor{frac{m}{t}} floor}i imes c_{it})^2 ]

我们发现后半坨式子可以边枚举 (t) 边算，复杂度是调和级数 (O(nln)) ，中间的 (sum mu(k) imes k) 可以预处理出来

所以整体复杂度是 (O(nln)) 的

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();};
        while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
        return x*f;
    }
    
    const int maxn = 5e4+5;
    int p[maxn],mu[maxn],f[maxn],c[maxn];
    bool vis[maxn];
    int n,m,cnt;
    long long ans=0,tmp;

    void init()
    {
        mu[1]=1;
        for(int i=2;i<=m;i++)
        {
            if(!vis[i])
            {
                p[++cnt]=i;
                mu[i]=-1;
            }
            for(int j=1;j<=cnt&&i*p[j]<=m;j++)
            {
                vis[i*p[j]]=true;
                if(i%p[j]==0)
                {
                    mu[i*p[j]]=0;
                    break;
                }
                mu[i*p[j]]=-mu[i];
            }
        }
        for(int i=1;i<=m;i++) for(int j=i;j<=m;j+=i) f[j]+=mu[i]*i;
    }

    void work()
    {
        int x;
        n=read();
        for(int i=1;i<=n;i++) x=read(),c[x]++,m=max(x,m);
        init();
        for(int t=1;t<=m;t++)
        {
            tmp=0;
            for(int i=1;i*t<=m;i++) tmp+=i*c[i*t];
            ans+=1ll*t*f[t]*tmp*tmp;
        }
        printf("%lld
",ans);
    }
}

int main()
{
    zzc::work();
    return 0;
}