傳送門ios
給出n個數 ,求 web
svg
再次被數論題制裁ui
太弱推不出式子來…atom
而後就去看了題解spa
咱們把h[i]設爲是i的倍數的a的兩兩數的積的總和,g[i]設爲gcd爲i的兩兩數的積的總和code
那麼有一個顯然的結論: xml
根據莫比烏斯反演公式咱們能夠知道 ip
最後咱們只須要求 便可get
咱們能夠快速的求出h,而後利用莫反求出g,最後複雜度
求h[i]咱們能夠先求出是i的倍數的a的和,而後再平方h便可(參考徹底平方公式)
代碼:
#include<cstdio>
#include<iostream>
using namespace std;
int n,a[50010];
long long h[50010],g[50010];
int vis[50010],N,prim[50010],cnt,miu[50010];
bool p[50010];
void get_prim(int n)
{
miu[1]=1;
for (int i=2;i<=n;i++)
{
if (!p[i]) prim[++cnt]=i,miu[i]=-1;
for (int j=1;j<=cnt&&prim[j]*i<=n;j++)
{
p[prim[j]*i]=1;
miu[prim[j]*i]=-miu[i];
if (i%prim[j]==0) {miu[i*prim[j]]=0;break;}
}
}
}
int main()
{
scanf("%d",&n);
for (int x,i=1;i<=n;i++) scanf("%d",&x),vis[x]++,N=max(N,x);
get_prim(N);
for (int i=1;i<=N;i++)
{
for (int j=i;j<=N;j+=i) h[i]+=1ll*j*vis[j];
h[i]*=h[i];
}
for (int i=1;i<=N;i++)
for (int j=i;j<=N;j+=i) g[i]+=miu[j/i]*h[j];
long long ans=0;
for (int i=1;i<=N;i++) ans+=g[i]/i;
printf("%lld",ans);
}