【刷题】BZOJ 4805 欧拉函数求和

Description

给出一个数字N,求sigma(phi(i)),1<=i<=N

Input

正整数N。N<=2*10^9文章来源地址https://www.yii666.com/article/756193.html文章地址https://www.yii666.com/article/756193.html文章来源地址:https://www.yii666.com/article/756193.html

Output

输出答案。网址:yii666.com

Sample Input

10

Sample Output

32

Solution

杜教筛裸题网址:yii666.com<

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=1000000+10;
int n,vis[MAXN],phi[MAXN],prime[MAXN],cnt;
ll s[MAXN];
std::map<int,ll> M;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void init()
{
memset(vis,1,sizeof(vis));
vis[0]=vis[1]=0;
phi[1]=1;
for(register int i=2;i<MAXN;++i)
{
if(vis[i])
{
prime[++cnt]=i;
phi[i]=i-1;
}
for(register int j=1;j<=cnt&&i*prime[j]<MAXN;++j)
{
vis[i*prime[j]]=0;
if(i%prime[j])phi[i*prime[j]]=phi[i]*phi[prime[j]];
else
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
for(register int i=1;i<MAXN;++i)s[i]=s[i-1]+phi[i];
}
inline ll S(int x)
{
if(x<MAXN)return s[x];
if(M[x])return M[x];
ll res=0;
for(register int i=2;;)
{
if(i>x)break;
int j=x/(x/i);
res+=1ll*(j-i+1)*S(x/i);
i=j+1;
}
return M[x]=1ll*(x+1)*x/2-res;
}
int main()
{
init();read(n);
write(S(n),'\n');
return 0;
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

【刷题】BZOJ 4805 欧拉函数求和-相关文章

  1. c语言总练习题

  2. BZOJ4805: 欧拉函数求和(杜教筛)

  3. BZOJ4802 欧拉函数 数论

  4. 【刷题】BZOJ 4805 欧拉函数求和

  5. BZOJ4802:欧拉函数(Pollard-Rho,欧拉函数)

  6. BZOJ 4802 欧拉函数

  7. bzo4802 欧拉函数 miller_rabin pollard_rho

  8. C++刷题——2830: 递归求1*1+2*2+3*3+……+n*n

      心得体会:这是一个简单递归函数,假设遇到复杂的递归函数。在写之前能够先找找规律,写成递归的形式。就比較好些了。继续努力。

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png