BZOJ-4916: 神犇和蒟蒻

Description

求和 n<=10^9

杜教筛
莫比乌斯函数那个是来搞笑的吧。
原式等于：


=
由于预处理前个，所以后面的所有记忆化搜索到的值 x 都大于，其搜索到的x对应的是两两不同的【我不会证】，所以可以不用哈希表了，直接将当做数组下标，最大不超过。时间复杂度

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll n,phi[2001000],Phi[2001000];
int pri[1001000],cnt;
bool v[2001000];
void initialize()
{
    phi[1]=1;
    for(int i=2;i<=2000000;++i)
    {
        if(!v[i]) pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;i*pri[j]<=2000000&&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=1;i<=2000000;++i)
        phi[i]=(phi[i]%mod*i%mod+phi[i-1])%mod;
}
ll squ(ll x) {return (x+1)*(2*x+1)%((mod<<1)+(mod<<2))*x/6%mod;}
ll calc(ll x)
{
    if(x<=2000000) return phi[x];
    if(Phi[n/x]) return Phi[n/x];
    ll re=squ(x); ll b=2,e;
    while(b<=x)
    {
        e=x/(x/b);
        re=(re-(e+b)*(e-b+1)/2%mod*calc(x/b)%mod+mod)%mod;
        b=e+1;
    }
    return Phi[n/x]=re;
}
int main()
{
    initialize();
    scanf("%lld",&n); 
    printf("1\n%lld\n",calc(n));
    return 0;
}