agc 038C
题意：给定$n$长序列$A_i$，求
$$
\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)
$$看起来很像莫反
我们推下式子
$$
\begin{align}
\mathrm{Ans}&=\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \mathrm{lcm}(A_i,A_j) \\
&=\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \frac{A_iA_j}{\gcd(A_i,A_j)} \\
\end{align}
$$
设$\sum\limits_{d|n} w(d)= \frac 1n$，则有
$$
\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} A_iA_j \sum_{d|A_i,d|A_j} w(d) \\
$$
交换一下顺序，得
$$
\sum_{d=1}^{V} w(d) \sum_{d|A_i,d|A_j,i \leq j,i \not=j} A_iA_j \\
$$
$w$很容易算，即$w(n)=\frac 1n - \sum\limits_{d|n, d \not= n} w(d)$，调和级数筛一下即可
考虑后面的怎么计算，因为权值范围$V$比较小，我们只需要统计每个权值出现几次即可。
对每个$d$，我们统计答案，即调和级数筛一下获得$A_i$中是$d$倍数$x$的数的和，然后将和自乘就是不考虑$i \leq j,i \not=j$的答案，考虑这个的话我们就在筛的时候顺便记录$x^2$的和，减去即可，然后除以二，但是要注意有重复数字，重复数字要再多乘一个数字出现次数。
放一个修改后更好理解的标程
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
return os<<"{"<<p.a<<","<<p.b<<"}";
}
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
os<<"{";
for(auto e:v)os<<e<<",";
return os<<"}";
}
using uint=unsigned;
using ull=unsigned long long;
const uint mod=998244353;
struct mint{
uint v;
mint(ll vv=0){s(vv%mod+mod);}
mint& s(uint vv){
v=vv<mod?vv:vv-mod;
return *this;
}
mint operator-()const{return mint()-*this;}
mint& operator+=(const mint&rhs){return s(v+rhs.v);}
mint&operator-=(const mint&rhs){return s(v+mod-rhs.v);}
mint&operator*=(const mint&rhs){
v=ull(v)*rhs.v%mod;
return *this;
}
mint&operator/=(const mint&rhs){return *this*=rhs.inv();}
mint operator+(const mint&rhs)const{return mint(*this)+=rhs;}
mint operator-(const mint&rhs)const{return mint(*this)-=rhs;}
mint operator*(const mint&rhs)const{return mint(*this)*=rhs;}
mint operator/(const mint&rhs)const{return mint(*this)/=rhs;}
mint pow(int n)const{
mint res(1),x(*this);
while(n){
if(n&1)res*=x;
x*=x;
n>>=1;
}
return res;
}
mint inv()const{return pow(mod-2);}
friend ostream& operator<<(ostream&os,const mint&m){
return os<<m.v;
}
bool operator<(const mint&r)const{return v<r.v;}
bool operator==(const mint&r)const{return v==r.v;}
};
const int vmax=(1<<21)+10;
mint fact[vmax],finv[vmax],invs[vmax];
void initfact(){
fact[0]=1;
rng(i,1,vmax){
fact[i]=fact[i-1]*i;
}
finv[vmax-1]=fact[vmax-1].inv();
for(int i=vmax-2;i>=0;i--){
finv[i]=finv[i+1]*(i+1);
}
for(int i=vmax-1;i>=1;i--){
invs[i]=finv[i]*fact[i-1];
}
}
mint choose(int n,int k){
return fact[n]*finv[n-k]*finv[k];
}
mint binom(int a,int b){
return fact[a+b]*finv[a]*finv[b];
}
mint catalan(int n){
return binom(n,n)-(n-1>=0?binom(n-1,n+1):0);
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
initfact();
const int v=1000010;
vc<mint> w(v);
rng(i,1,v){
w[i]+=invs[i];
for(int j=i*2;j<v;j+=i)
w[j]-=w[i];
}
int n;cin>>n;
mint ans=0;
vc<mint> s(v);
rep(i,n){
int a;cin>>a;
s[a]+=a;
}
rng(i,1,v){
mint x=0,gg=0;
for(int j=i;j<v;j+=i)x+=s[j],gg+=s[j].v*j;
ans+=(x*x-gg)/2*w[i];
}
cout<<ans<<endl;
}
