首页 > 其他 > 详细

BZOJ 4805: 欧拉函数求和 杜教筛

时间:2019-06-26 13:46:09      阅读:139      评论:0      收藏:0      [点我收藏+]

Code:

#include<bits/stdc++.h>
#define maxn 10000004
#define  ll long long 
#define M 1000002  
using namespace std;
void setIO(string s)
{
	string in=s+".in"; 
	freopen(in.c_str(),"r",stdin); 
}
int cnt; 
bool vis[maxn]; 
int prime[maxn], phi[maxn]; 
ll sumv[maxn]; 
ll Sum(ll n) { return (n * (n + 1)) / 2;  }
inline void Init()
{ 
	int i,j;
	phi[1]=1; 
	for(i=2;i<=M;++i)
	{
		if(!vis[i]) prime[++cnt]=i, phi[i]=i-1; 
		for(j=1;j<=cnt&&1ll*prime[j]*i<=M;++j)
		{
			vis[prime[j]*i]=1; 
			if(i%prime[j]==0) 
			{
				phi[i*prime[j]]=phi[i]*prime[j]; 
				break; 
			}
			phi[i*prime[j]]=phi[i]*(prime[j]-1); 
		}
	} 
	for(i=1;i<=M;++i) sumv[i]=sumv[i-1]+1ll*phi[i]; 
}
map<int,ll>sumphi; 
ll get(int n)
{
	if(n<=M) return 1ll*sumv[n]; 
	if(sumphi[n]) return sumphi[n]; 
	ll re=1ll*Sum(n); 
	int i,j; 
	for(i=2;i<=n;i=j+1)
	{
		j=n/(n/i); 
		re -= 1ll*(j-i+1) * 1ll*get(n/i); 
	}
	return re; 
}
int main()
{
	// setIO("input"); 
	Init();  
	int n; 
	scanf("%d",&n);  
	printf("%lld\n",get(n)); 
	return 0; 
}

  

BZOJ 4805: 欧拉函数求和 杜教筛

原文:https://www.cnblogs.com/guangheli/p/11089250.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!