洛谷 3911 最小公倍数之和

首先设 lim=Nmaxi=1ai,ck=N∑i=1[ai=k]。
于是问题转化为求解 lim∑i=1lim∑j=1lcm(i,j)cicj。

lim∑i=1lim∑j=1lcm(i,j)cicj=lim∑i=1lim∑j=1ijcicjgcd(i,j)=lim∑d=1d∑id≤lim∑jd≤lim[gcd(i,j)=1]ijcidcjd

设 f(x)=∑id≤lim∑jd≤lim[gcd(i,j)=x]ijcidcjd,F(x)=∑x|df(d)=∑id≤lim∑jd≤lim[x|gcd(i,j)]ijcidcjd。

F(x)=∑id≤lim∑jd≤lim[x|gcd(i,j)]ijcidcjd=x2∑xid≤lim∑xjd≤limijcixdcjxd=x2(∑xid≤limicixd)2

lim∑d=1d∑id≤lim∑jd≤lim[gcd(i,j)=1]ijcidcjd=lim∑d=1df(1)=lim∑d=1d∑id≤limi2μ(i)(∑ijd≤limjcijd)2

于是可以预处理 (∑xd≤limjcxd)2 然后这题就没了。

代码：

#include <cstdio>
using namespace std;
const int N = 5e4;
int n,lim,c[N + 5];
int vis[N + 5],prime[N + 5],cnt,mu[N + 5];
long long f[N + 5];
long long ans;
int main()
{
    mu[1] = 1;
    for(register int i = 2;i <= N;++i)
    {
        if(!vis[i])
            mu[prime[++cnt] = i] = -1;
        for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    scanf("%d",&n);
    int x;
    for(register int i = 1;i <= n;++i)
        scanf("%d",&x),++c[x],lim = max(lim,x);
    for(register int i = 1;i <= lim;f[i] *= f[i],++i)
        for(register int j = 1;i * j <= lim;++j)
            f[i] += (long long)j * c[i * j];
    for(register int i = 1;i <= lim;++i)
        for(register int j = 1;i * j <= lim;++j)
            ans += (long long)i * j * j * mu[j] * f[i * j];
    printf("%lld\n",ans);
}