题目链接：https://codeforces.com/gym/103688/problem/E
题意：
算法：莫比乌斯反演 时间复杂度 O(nlogn)
解法：
时间复杂度:O（nlogn）
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
#define lmw ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e6+10;
int s[N],m[N],sum[N],f[N];
int cnt;
int a[N];
int l[N],h[N],p[N];
const int mod=1e9+7;
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
void unit(int N){
m[1]=1;f[1]=1;
for(int i=2;i<=N;i++){
if(!a[i]){
s[cnt++]=i;
m[i]=-1;
f[i]=i;
l[i]=1;
}
for(int j=0;s[j]*i<N&&j<cnt;j++){
a[s[j]*i]=1;
if(i%s[j]==0){
if(l[i]&1) f[s[j]*i]=f[i]/s[j];
else f[s[j]*i]=f[i]*s[j];
l[s[j]*i]=l[i]^1;
break;
}
f[s[j]*i]=f[i]*s[j];
l[s[j]*i]=1;
m[s[j]*i]=m[i]*-1;
}
}
}
signed main(){
int n;
n=read();
unit(N);
int maxl=0;
for(int i=1;i<=n;i++){
int x;
x=read();
h[x]++;
maxl=max(maxl,x);
}
int sum=0;
for(int i=1;i<=maxl;i++){
for(int j=i;j<=maxl;j+=i){
int num=0;
for(int k=1;k<=(maxl/j);k++){
num=(num+f[i*k]*h[j*k]%mod)%mod;
}
num=num*num%mod;
p[j]=(p[j]+m[i]*num%mod+mod)%mod;
}
sum=(sum+p[i])%mod;
}
cout<<(sum-n+mod)%mod*500000004%mod;
}