洛谷P3911 最小公倍數之和-莫比烏斯反演

傳送門ios

題意：

給出n個數$a_i$，求$\sum_{i=1}^n\sum_{j=1}^n lcm(a_i,a_j)$web

$1 \le N \le 50000; 1 \le a_i \le 50000$svg

Solution：

再次被數論題制裁ui

太弱推不出式子來…atom

而後就去看了題解spa

咱們把h[i]設爲是i的倍數的a的兩兩數的積的總和，g[i]設爲gcd爲i的兩兩數的積的總和code

那麼有一個顯然的結論：$h(i)=\sum_{i|j}g(j)$xml

根據莫比烏斯反演公式咱們能夠知道$g(i)=\sum_{i|j}\mu(\frac j i)h(j)$ip

最後咱們只須要求$\sum_{i=1} \frac {g(i)}{i}$便可get

咱們能夠快速的求出h，而後利用莫反求出g，最後複雜度$O(n+\frac n 2+\frac n 3...)=O(n \log n)$

求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);
}