返回首页 返回专题

【UVA11417】【LuoguP2398】GCD 题解

这题的UVA版本是入门题，直接大力O(T n² lg n)枚举即可AC（lg n是辗转相除法的时间复杂度）

所以我们不管它，我们来看洛谷版本，显然O(n² lg n)行不通了

画柿子！

维护2phi(x)的前缀和，f(p)即可O(1)求解

答案就是sigma{p*f(p)}(p=1~n)

时间复杂度O(n)

网上有一些看似非常简短的代码，复杂度O(n log n)，相当垃圾，而且计算方法不好理解

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=500;
LL phi[N+10];
int prime[95+10],tot=0;
bool mark[N];

void Init()
{
	memset(mark,0,sizeof(mark));
	for(int i=2;i<=N;i++)
	{
		if(!mark[i]) prime[++tot]=i,phi[i]=i-1;
		for(int j=1;j<=tot&&i*prime[j]<=N;j++)
		{
			mark[i*prime[j]]=1;
			if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
			else phi[i*prime[j]]=phi[i]*prime[j];
		}
	}
	phi[1]=0;
	for(int i=2;i<=N;i++) phi[i]=phi[i-1]+phi[i];
}

int main()
{
	Init();
	int n;
	while(cin>>n&&n)
	{
		LL ans=0;
		for(int i=1;i<=n;i++)
			ans+=(LL)i*phi[n/i];
		cout<<ans<<endl;
	}
	return 0;
}