BZOJ-4805: 欧拉函数求和

Description

给出一个数字N，求,n<=10^9

杜教筛
我们知道，那么则有
那么
枚举i/d :
即：
对于相同的我们可以分块，之后对于每个进行记忆化搜索，预处理前的值，对于一个询问可以做到出解。

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pb push_back
ll phi[1001000];
int pri[501000],cnt;
bool v[1001000];
void initialize()
{
    phi[1]=1;
    for(int i=2;i<=1000000;++i)
    {
        if(!v[i]) pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;i*pri[j]<=1000000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]) phi[i*pri[j]]=phi[i]*pri[j]-phi[i];
            else {phi[i*pri[j]]=phi[i]*pri[j]; break;}
        }
    }
    for(int i=2;i<=1000000;++i) phi[i]+=phi[i-1];
}
struct Hash
{
    struct node
    {
        int x; ll ans;
    };
    vector<node>vec[1000003];
    ll query(int x)
    {
        int id=x%1000003;
        for(int i=0;i<(int)vec[id].size();++i)
            if(vec[id][i].x==x) return vec[id][i].ans;
        return -1;
    }
    void insert(int x,ll ans)
    {
        vec[x%1000003].pb((node){x,ans});
    }
}ha;
ll calc(ll x)
{
    if(x<=1000000) return phi[x];
    ll re=ha.query(x); 
    if(re!=-1) return re;
    re=x*(x+1)/2; ll b=2,e;
    while(b<=x)
    {
        e=x/(x/b);
        re-=calc(x/b)*(e-b+1);
        b=e+1;
    }
    ha.insert(x,re);
    return re;
}
ll n;
int main()
{
    scanf("%lld",&n); initialize();
    printf("%lld\n",calc(n));
    return 0;
}