题解 P2398 【GCD SUM】

· · 题解

贴一篇不需要反演的题解。

直接计算复杂度过高无法接受

考虑枚举所有gcd值计算

若gcd=k

对于所有gcd\left ( x,y \right )=1，有gcd\left ( xk,yk \right )=k\left ( xk\leq n,yk\leq n \right )

所以gcd=k的个数为

2*\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\varphi \left ( i \right )-1 线性筛一遍欧拉函数，然后求前缀和 复杂度$O\left ( n \right ) 
#include<cstdio>
#define LL long long
const int N=100050;
int prime[N],cnt=0,phi[N];
LL n,sum[N],ans=0;
void init()
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if (!phi[i]) prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt;j++)
        {
            if (prime[j]*i>n) break;
            if (i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }       
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];
}
int main()
{
    scanf("%lld",&n);
    init();
    for(LL i=1;i<=n;i++) 
        ans+=(sum[n/i]*2-1)*i;
    printf("%lld",ans);
    return 0;
}