给定长度为 \(N\) 的序列 \(A\)，求：
\[\sum_{i=1}^N\sum_{j=1}^N\operatorname {lcm}(A_i,A_j) \]利用小学知识可以化成：
\[\sum_{i=1}^N\sum_{j=1}^N\frac{A_i\times A_j}{\gcd(A_i,A_j)} \]考虑到 \(A_i\le5\times 10^4\)。
开一个桶 \(a\)，\(a_i=\sum_{j=1}^N[A_j=i]\)。
设 \(n\) 为 \(\max_{A_i},i\in[1,N]\)。
原式子就可以化成：
\[\sum_{i=1}^n\sum_{j=1}^n a_i\times a_j\times \frac{i\times j}{\gcd(i,j)} \] \[=\sum_{d=1}^n d\times \sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor} a_{i\times d}\times a_{j\times d}\times i\times j\times [\gcd(i,j)=1] \] \[=\sum_{d=1}^n d\times \sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor} a_{i\times d}\times a_{j\times d}\times i\times j\times \sum_{p|\gcd(i,j)}\mu(p) \] \[=\sum_{d=1}^n d\times \sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(p)\times p^2 \times \sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor} \sum_{j=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}a_{i\times d\times p}\times a_{j\times d\times p}\times i\times j \]在去掉 \(a_{i\times d\times p}\times a_{j\times d\times p}\) 的时候， \(\sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor} \sum_{j=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}i\times j\) 是可以 \(\operatorname O(1)\) 运算出来的，可以实现 \(\operatorname O(n\sqrt n)\)，即 \(d\) 这一层直接枚举，然后 \(p\) 这一层用整除分块优化。
那么这个 \(a\) 该怎么考虑呢？
提取 \(d\times p\)，化为：
\[\sum_{T=1}^nT\times \sum_{p|T}\mu(p)\times p\times \sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor} \sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor}a_{i\times T}\times a_{j\times T}\times i\times j \]设
\[s_i=i\times \sum_{p|i}\mu(p)\times p \]这个 \(s\) 是可以预处理的东西。
原式可化为：
\[\sum_{T=1}^ns_T\times \sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor} \sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor}a_{i\times T}\times a_{j\times T}\times i\times j \]把 \(i\) 提到自己那一层：
\[\sum_{T=1}^n s_T\times \sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}a_{i\times T}\times i\times \sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor}a_{j\times T}\times j \]这里后面两个 \(\sum\) 之间并没有联系，实际上可以看成：
\[\sum_{T=1}^n s_T\times (\sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}a_{i\times T}\times i)\times (\sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor}a_{j\times T}\times j) \]后面两项是相同的，所以提取公因式，得到：
\[\sum_{T=1}^n s_T\times (\sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}a_{i\times T}\times i)^2 \]惊喜的发现后面这个也是可以预处理的，两个预处理之后就可以直接枚举 \(T\) 求答案了。
虽然看着后面这个东西很像整除分块的式子，但因为内部有一个 \(a_{i\times T}\)，这个东西下标中含有 \(T\)，所以并不能整除分块。
实际上从另一个角度理解，就跟 \(\left\lfloor \frac{n}{T} \right\rfloor\) 这一项没有关系了。具体的操作，设函数 \(g\)，满足：
\[g_T=(\sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}a_{i\times T}\times i)^2 \]\(g_T\) 是所有满足是 \(T\) 的倍数的数能对它产生贡献。
本身这个复杂度也是能够接受的范围，也不需要去整除分块优化。
虽然我算不来这个理论复杂度
#include <bits/stdc++.h>
#define LL long long
#define max(a,b) a>b?a:b
using namespace std;
const int MAN=5e4;
bool bj[MAN+3];
int mu[MAN+3];
int d[MAN+3];
LL a[MAN+3];
LL s[MAN+3];
LL g[MAN+3];
int tail;
int n,N;
LL rin()
{
LL s=0;
char c=getchar();
bool bj=false;
for(;(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')c=getchar(),bj=true;
for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^'0');
if(bj)return -s;
return s;
}
int main()
{
N=rin();
int x;
for(int i=1;i<=N;i++)
{
x=rin();
a[x]++;
n=max(n,x);
}
//第二个东西的预处理
for(int i=1;i<=n;i++)
{
for(int j=1;true;j++)
{
int now=i*j;
if(now>n)break;
g[i]+=a[now]*j;
}
g[i]=g[i]*g[i];
}
mu[1]=1;
tail=0;
for(int i=2;i<=n;i++)
{
if(!bj[i])mu[i]=-1,d[++tail]=i;
for(int j=1;j<=tail;j++)
{
int now=i*d[j];
if(now>n)break;
bj[now]=true;
if(i%d[j]==0)break;
mu[now]=-mu[i];
}
}
//s的预处理
for(int i=1;i<=n;i++)
for(int j=1;true;j++)
{
int now=i*j;
if(now>n)break;
s[now]+=mu[i]*i;
}
LL ans=0;
for(int i=1;i<=n;i++)ans+=s[i]*g[i]*i;
printf("%lld",ans);
return 0;
}