题意:

戳这里

分析：

• 推柿子

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

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

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

所以整体复杂度是 \(O(n\ln)\) 的

代码：

#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\n",ans);
    }
}

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