AT5200 [AGC038C] LCMs 莫比乌斯反演

题意：

戳这里

分析：

大力推柿子：

[sum_{i=1}^nsum_{j=i+1}^nfrac{a_ia_j}{gcd(a_i,a_j)} \ =frac{displaystylesum_{i=1}^nsum_{j=1}^nfrac{a_ia_j}{gcd(a_i,a_j)}-sum_{i=1}^na_i}{2} \ =frac{displaystylesum_{d=1}^msum_{i=1}^nsum_{j=i+1}^nfrac{a_ia_j}{d}[d==gcd(a_i,a_j)]-sum_{i=1}^na_i}{2} \ =frac{displaystylesum_{d=1}^msum_{t=1}^{lfloor{frac{m}{d} floor}}frac{mu(t)}{d}(sum_{i=1}^na_i[td|a_i])^2-sum_{i=1}^na_i}{2} ]

我们设 (displaystyle f(x)=(sum_{i=1}^na_i[td|a_i])) 这个东西可以利用调和级数做到 (O(mlog m))

代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register

using namespace std;

namespace zzc
{
    typedef long long ll;
    inl ll read()
    {
        ll x=0,f=1;char ch=getchar();
        while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
        return x*f;
    }

    const ll maxn = 2e5+5;
    const ll maxm = 1e6+5;
    const ll mod = 998244353;
    ll n,cnt,m,ans;
    ll a[maxn],inv[maxm],mu[maxm],p[maxm],f[maxm],t[maxm];
    bool vis[maxm];

    void init()
    {
        mu[1]=1;inv[0]=inv[1]=1;
        for(reg int i=2;i<=m;i++)
        {
            inv[i]=inv[mod%i]*(mod-mod/i)%mod;
            if(!vis[i])
            {
                p[++cnt]=i;
                mu[i]=-1;
            }
            for(reg int j=1;j<=cnt&&i*p[j]<=m;j++)
            {
                vis[i*p[j]]=true;
                if(i%p[j]==0)
                {
                    mu[i*p[j]]=0;
                    break;
                }
                mu[i*p[j]]=-mu[i];
            }
        }
        for(reg int i=1;i<=n;i++) t[a[i]]++;
        for(reg int i=1;i<=m;i++) for(reg int j=i;j<=m;j+=i) f[i]=(f[i]+t[j]*j%mod)%mod;
    }

    void work()
    {
        n=read();
        for(reg int i=1;i<=n;i++) a[i]=read(),m=max(m,a[i]),ans=(ans-a[i]+mod)%mod;
        init();
        for(reg int d=1;d<=m;d++) for(reg int t=1;t*d<=m;t++) ans=(ans+(mu[t]+mod)%mod*inv[d]%mod*f[t*d]%mod*f[t*d]%mod)%mod;
        printf("%lld
",(ans*inv[2]%mod+mod)%mod);
    }

}

int main()
{
    zzc::work();
    return 0;
}