题解 SP5971 【LCMSUM - LCM Sum】

· · 题解

欧拉函数。算是对 @BJpers2 巨佬的代码补充。

本文同步发表于笔者的博客：题解 SP5971 LCMSUM - LCM Sum

推公式过程如下：

\sum_{i=1}^{n}lcm(i,n)=\sum_{i=1}^{n}{in\over gcd(i,n)}=n\sum_{i=1}^{n}{i\over gcd(i,n)}

转化 gcd：

=n\sum_{d|n}\sum_{i=1}^{n}{i\over d}[gcd(i,n)=d] =n\sum_{d|n}\sum_{i=1}^{n\over d}{i\over d}[gcd(id,n)=d] =n\sum_{d|n}\sum_{i=1}^{n\over d}i[gcd(i,{n\over d})=1] =n\sum_{d|n}\sum_{i=1}^{d}i[gcd(i,d)=1]

后面这个等于 {φ(d)d}\over 2，所以原式最终为：

=n\sum_{d|n}{{φ(d)d}\over 2}

可以预处理时把每个 i 的倍数加上 {φ(i)i}\over 2，然后最后输出时乘上 n。（i 等于 1 时值为 1）。

#include<bits/stdc++.h>
#define MAXN 1000000
#define ll long long
using namespace std;
int pri[MAXN+5],tot,phi[MAXN+5];
ll f[MAXN+5];
bool isp[MAXN+5];
void GetPrime()
{
    phi[1]=1;
    isp[1]=1;
    for(int i=2;i<=MAXN;i++)
    {
        if(!isp[i])
        {
            pri[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=tot && i*pri[j]<=MAXN;j++)
        {
            isp[i*pri[j]]=1;
            if(i%pri[j]) phi[i*pri[j]]=phi[i]*phi[pri[j]];
            else
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
        }
    }
    for(int i=1;i<=MAXN;i++)
    {
        for(int j=1;i*j<=MAXN;j++) f[i*j]+=(i==1?1:1ll*phi[i]*i/2);
    }
}
int main()
{
    GetPrime();
    int Time;
    scanf("%d",&Time);
    while(Time--)
    {
        int n;
        scanf("%d",&n);
        printf("%lld\n",f[n]*1ll*n);
    }
    return 0;
}