bzoj 4805: 欧拉函数求和

Time Limit: 15 Sec Memory Limit: 256 MB
Submit: 539 Solved: 304
[Submit][Status][Discuss]

Description

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

Input

正整数N。N<=2*10^9

Output

输出答案。

Sample Input

Sample Output

HINT

Source

By FancyCoder

杜教筛模板题，好久没打了练练手hhh

(一开始把i和j写反了WA了一墙hhhh)

/**************************************************************
    Problem: 4805
    User: JYYHH
    Language: C++
    Result: Accepted
    Time:1524 ms
    Memory:64772 kb
****************************************************************/
 
#include<bits/stdc++.h>
#define ll unsigned long long
#define maxn 5000000
using namespace std;
map<ll,ll> mmp;
int zs[maxn+5],t=0;
ll phi[maxn+5],n;
bool v[maxn+5];
 
inline void init(){
    phi[1]=1;
    for(int i=2;i<=maxn;i++){
        if(!v[i]) zs[++t]=i,phi[i]=i-1;
        for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){
            v[u]=1;
            if(!(i%zs[j])){
                phi[u]=phi[i]*zs[j];
                break;
            }
            phi[u]=phi[i]*(zs[j]-1);
        }
    }
     
    for(int i=1;i<=maxn;i++) phi[i]+=phi[i-1];
}
 
inline ll sum(ll x){
    if(x<=maxn) return phi[x];
    if(mmp.count(x)) return mmp[x];
    ll ans=x*(x+1)>>1ll,j;
    for(ll i=2;i<=x;i=j+1){
        j=x/(x/i);
        ans-=sum(x/i)*(j-i+1);
    }
    mmp[x]=ans;
    return ans;
}
 
int main(){
    init();
    scanf("%llu",&n);
    printf("%llu
",sum(n));
    return 0;
}