C++(g++ 7.5.0) 解法, 执行用时: 367ms, 内存消耗: 26904K, 提交时间: 2022-08-05 16:55:11

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
typedef long long ll;
const int mod = 998244353;

ll cnt[N];
ll sum[N];
ll a[N];
ll inv[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        cnt[a[i]]++;
    }
    inv[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
    ll ans=0;
    for(int i=1000000;i>=1;i--)
    {
        ll s1=0,s2=0;
        for(int j=i;j<=1000000;j+=i)
        {
            s1=(s1+cnt[j]*j%mod)%mod;
            s2=(s2+cnt[j]*j%mod*j%mod)%mod;
        }
        sum[i]=(s1*s1%mod-s2+mod)%mod*inv[2]%mod;
        for(int j=(i<<1);j<=1000000;j+=i)
        {
            sum[i]=(sum[i]-sum[j]+mod)%mod;
        }
        ans=(ans+inv[i]*sum[i]%mod)%mod;
    }
    cout<<ans<<endl;
}

C++ 解法, 执行用时: 646ms, 内存消耗: 12940K, 提交时间: 2021-10-29 18:47:43

//先存个答案qwq
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=200010,K=1000010,p=998244353;
int inv[K],sum[K],a[N],n,cnt[K];
int main(){
    scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d",&a[i]),++cnt[a[i]];
    inv[1]=1;for(int i=2;i<K;++i) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
    int ans=0;
    for(int i=K-1;i;--i){
        int s1=0,s2=0;
        for(int j=i;j<K;j+=i) s1=(s1+1ll*cnt[j]*j%p)%p,s2=(s2+1ll*cnt[j]*j%p*j%p)%p;
        sum[i]=1ll*(1ll*s1*s1%p-s2+p)*inv[2]%p;
        for(int j=(i<<1);j<K;j+=i) sum[i]=(sum[i]-sum[j]+p)%p;
        // if(i<10) printf("%d %d %d %d %d\n",i,sum[i],s1,s2,inv[i]);
        ans=(ans+1ll*inv[i]*sum[i]%p)%p;
    }
    printf("%d\n",ans);
    return 0;
}