题解P3911 最小公倍数之和

以下用 $m$ 代表 $max(A_i)$, $c(i)$ 表示 $i$ 出现的次数

法一:

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^nlcm(A_i, A_j)=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\frac{A_iA_j}{gcd(A_i,A_j)}\\=\sum\limits_{d=1}^m\frac{1}{d}\sum\limits_{i=1}^m\sum\limits_{j=1}^m\frac{ij}{d}c(i)c(j)[gcd(i,j)=d]\\=\sum\limits_{d=1}^md\sum\limits_{i=1}^{\frac{m}{d}}\sum\limits_{j=1}^{\frac{m}{d}}ijc(id)c(jd)[gcd(i,j)=1]\\=\sum\limits_{d=1}^md\sum\limits_{i=1}^{\frac{m}{d}}\sum\limits_{j=1}^{\frac{m}{d}}ijc(id)c(jd)\sum\limits_{k|gcd(i,j)}\mu(k)\\=\sum\limits_{d=1}^m\sum\limits_{k=1}^{\frac{m}{d}}\sum\limits_{i=1}^{\frac{m}{kd}}\sum\limits_{j=1}^{\frac{m}{kd}}dijc(idk)c(jdk)\mu(k)k^2\\=\sum\limits_{T=1}^mT\sum\limits_{k|T}^m\mu(k)k(\sum\limits_{i=1}^{\frac{m}{T}}ic(iT))^2$$

前面可以 $O(n)$ 预处理,后面直接暴力枚举

法二

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^nlcm(A_i,A_j)=\sum\limits_{d=1}^m\sum\limits_{i=1}^n\sum\limits_{j=1}^n\frac{A_iA_j}{d}[gcd(A_i,A_j)=d]\\=\sum\limits_{d=1}^m\frac{1}{d}\sum\limits_{i=1}^n\sum\limits_{j=1}^nA_iA_j[d|A_i][d|A_j][gcd(\frac{A_i}{d},\frac{A_j}{d})=1]\\=\sum\limits_{d=1}^m\frac{1}{d}\sum\limits_{i=1}^n\sum\limits_{j=1}^nA_iA_j[d|A_i][d|A_j]\sum\limits_{k|gcd(\frac{A_i}{d},\frac{A_j}{d})}\mu(k)\\=\sum\limits_{d=1}^m\sum\limits_{k=1}^{\frac{m}{d}}\frac{\mu(k)}{d}\sum\limits_{i=1}^n\sum\limits_{j=1}^nA_iA_j[kd|A_i][kd|A_j]\\=\sum\limits_{d=1}^m\sum\limits_{k=1}^{\frac{m}{d}}\frac{\mu(k)}{d}(\sum\limits_{i=1}^nA_i[kd|A_i])^2\\=\sum\limits_{d=1}^m\sum\limits_{k=1}^{\frac{m}{d}}\frac{\mu(k)}{d}(\sum\limits_{kd|i}^mic(i))^2$$

后面一坨可以 $O(n\log(n))$ 预处理

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 50005;
typedef long long ll;

bool st[N];
int prime[N], tot, n;
int a[N], c[N], m, mu[N];
ll sum[N];

void init()
{
    mu[1] = 1;
    for (int i = 2; i <= m; i++)
    {
        if (!st[i])
            prime[++tot] = i, mu[i] = -1;
        for (int j = 1; i * prime[j] <= m; j++)
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= m; i++)
        for (int j = i; j <= m; j += i)
            sum[j] += mu[i] * i;
}

int main()
{
    scanf("%d", &n);   
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        c[a[i]]++, m = max(m, a[i]);
    }
    init();
    ll ans = 0;
    for (int i = 1; i <= m; i++)
    {
        ll temp = 0;
        for (int j = 1; j <= m / i; j++)
            temp += (ll)j * c[j * i];
        ans += (ll)i * sum[i] * temp * temp;        
    }
    printf("%lld", ans);
    return 0;
}