[Solution][数论]Sum of LCM

【题目】

戳这里

【题意】

给出序列,求出

数据范围:

【思路】

蒟蒻又被虐了。。。不过从中受益匪浅。。。

暴力想法直接枚举,这样是的,分。

尝试将其离散化,设表示序列中数的出现次数。

设序列中数的最大值为.

显然我们可以将其转化为:

即:

我们枚举值,以表示。再枚举使得.

于是化为:

函数e表示单位函数,即对于正整数,当且仅当满足,否则.

这是显然的,这样能保证枚举出的互质。

表示的莫比乌斯函数,再进行整理:

这里为什么呢???(莫比乌斯反演)

提出:

尝试改为枚举的公约数,再枚举,使得.

这样就有:

在后面提出一个,就有:

再改为枚举的乘积,化为:

注意到可以继续化简:

到此我们的任务基本上完成了。

的欧拉线性筛预处理,再利用以一种类似于埃斯托拉尼筛法在预处理出每一个

接着只需枚举,再枚举计算出后一段,算出乘积累加就行了。

事实证明总的时间复杂度是的。

【代码】

#include<cstdio>
#include<cstring>
#define N (50000)
typedef long long LL;
int prime[50010] , top , mobius[50010],  get[50010];
bool notprime[50010];
int num[50010];
int main()
{
    register int i , j;
    mobius[1] = 1;
    for(i = 2 ; i <= N ; ++i)
    {
        if (!notprime[i])
        {
            prime[++top] = i;
            mobius[i] = -1;
        }
        for(j = 1 ; j <= top ; ++j)
        {
            if (i * prime[j] > N)
                break;
            notprime[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                mobius[i * prime[j]] = 0;
                break;
            }
            else
                mobius[i * prime[j]] = -mobius[i];
        }
    }
    for(i = 1 ; i <= N ; ++i)
        for(j = i ; j <= N ; j += i)
            get[j] += i * mobius[i];
    int n;
    scanf("%d" , &n);
    int x;
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%d" , &x);
        ++num[x];
    }
    LL res = 0;
    for(i = 1 ; i <= N ; ++i)
    {
        LL add = 0;
        for(j = 1 ; j * i <= N ; ++j)
            add += j * num[j * i];
        res += add * add * i * get[i];
    }
    printf("%lld" , res);
    return 0;
}
comments powered by Disqus