zcmimi's blog
查看原题

点击跳转

\sum_{i=1}^n\sum_{j=1}^n lcm(A_i,A_j)

a_i = \sum_{j=1}^n [A_j=i]

那么

ans = \sum_i^n \sum_j^n a_ia_j \frac{ij}{\gcd(i,j)} \\ = \sum_{d=1}^n \frac 1d \sum_{i=1}^n \sum_{j=1}^n a_ia_j ij[\gcd(i,j)=d] \\ = \sum_{d=1}^n \sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd}d \times a_{id}a_{jd}ij[\gcd(i,j)=1] \\ \text{唉,到这里我就不会了} \\ =\sum_{p=1}^np\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}a_{ip}a_{jp}ij\sum_{d|i,d|j}\mu(d) \\ =\sum_{p=1}^np\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{n/dp}\sum_{j=1}^{n/dp}a_{idp}a_{jdp}ij \\ =\sum_{q=1}^nq\sum_{d|q}d\mu(d)\sum_{i=1}^{n/q}\sum_{j=1}^{n/q}a_{iq}a_{jq}ij \\ =\sum_{q=1}^nq\sum_{d|q}d\mu(d)\left(\sum_{i=1}^{n/q}a_{iq}i\right)^2

#include <cstdio>
using namespace std;

int prime[50010], mu[50010], tot, fuck = 50000;
bool vis[50010];
long long sum1[50010], sum2[50010];
int bucket[50010];

int main(){
    mu[1] = 1;
    for (int i = 2; i <= fuck; i++){
        if (vis[i] == false) prime[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * prime[j] <= fuck; j++){
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
        mu[i] *= i;
    }
    for (int d = 1; d <= fuck; d++)
        for (int q = d; q <= fuck; q += d)
            sum1[q] += mu[d];
    for (int i = 1; i <= fuck; i++)
        sum1[i] *= i;
    int n; scanf("%d", &n);
    for (int x, i = 1; i <= n; i++)
        scanf("%d", &x), bucket[x]++;
    long long ans = 0;
    for (int q = 1; q <= fuck; q++){
        int sb = fuck / q;
        for (int i = 1; i <= sb; i++)
            sum2[q] += bucket[i * q] * (long long)i;
        ans += sum2[q] * sum1[q] * sum2[q];
    }
    printf("%lld\n", ans);
    return 0;
}
LG 3911 最小公倍数之和
comment评论
Search
search