自动搬运

查看原文

来自洛谷，原作者为

	Kelin 这个家伙太菜，没什么可以留下的

搬运于2025-08-24 21:24:33，当前版本为作者最后更新于2017-08-06 20:08:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实这题和P2389差不多还简单一些

这里介绍一种nlogn的做法

设f[d]=∑∑gcd(i,j)=d

F[d]=∑∑d|gcd(i,j)

不难看出F[d]=n/d*(n/d)

那么f[d]=F[d]-∑f[kd]

所以o(nlogn)扫一下就好了（主要是代码特别短）

然后ans=(∑f[d]-n*(n+1)/2)/2 减去gcd(d,d)=d的和gcd(i,j)=gcd(j,i)重复的

#include<cstdio>
#define re register int
long long n,ans,f[2000010];
int main(){
    scanf("%lld",&n);
    for(re i=n;i;--i){
        f[i]=n/i*(n/i);
        for(re j=i<<1;j<=n;j+=i)f[i]-=f[j];
        ans+=f[i]*i;
    }
    printf("%lld",(ans-n*(n+1)/2)/2);
return 0;
}