杜教篩--51nod1239 歐拉函數之和

求$\sum_{i=1}^{n}\varphi (i)$，$n\leqslant 1e10$。

這里先把杜教篩的一般套路貼一下：

要求$S(n)=\sum_{i=1}^{n}f(i)$，而現在有一數論函數$g(i)$，$g(i)$的前綴和很無腦，且$f$和$g$的狄利克雷卷積的前綴和很無腦（太巧了吧。。），那么由

$\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})$

閃一句，常用套路：設$i=kd$，轉而枚舉$k$。

$=\sum_{k=1}^{n}g(k)\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}f(d)$

$=\sum_{k=1}^{n}g(k)S(\frac{n}{k})$

可得

$g(1)S(n)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})-\sum_{k=2}^{n}g(k)S(\left \lfloor \frac{n}{k} \right \rfloor)$

進而遞推求S。

官方復雜度：（假如構造的卷積的前綴和和g的前綴和都是O(1)可知）由于S那個除法的取值范圍：1，2，……，m-1，m，n/m，n/(m-1)，……，n，

可以想到預處理一部分再算一部分，假設預處理了$n^k$，那么總的復雜度就是：$max(n^k,沒預處理的那一段)$，

沒預處理的那段就是$\sum_{i=1}^{n^{1-k}}\sqrt{\frac{n}{i}}=n^{\frac{1}{2}}\sum_{i=1}^{n^{1-k}}i^{-\frac{1}{2}}\approx n^{\frac{1}{2}}n^\frac{1-k}{2}$

所以總的復雜度就是$max(n^k,n^{\frac{1}{2}}n^\frac{1-k}{2})$，當$\frac{1}{2}+\frac{1-k}{2}=k$時取得最小復雜度，$k=\frac{2}{3}$.

然而我這里有點不懂：因為沒預處理的那段我們是直接遞歸+記憶化的，那記憶化的那部分復雜度怎么算？如何證明杜教篩過程中出現的數字個數的上限？暫不知。先用著。

好那這道題，我們要找一個前綴和無腦且和$\varphi $乘起來無腦的一個函數--1！——就是f(x)=1不知道叫什么——因為有$\varphi *1=Id$，$Id(x)=x$。

那就帶進去玩一玩：

$\sum_{i=1}^{n}\sum_{d|i}\varphi (d)=\sum_{k=1}^{n}1\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\varphi (d)= \sum_{k=1}^{n}S(\left \lfloor \frac{n}{k} \right \rfloor)$

玩夠一百下再玩一百下：

$S(n)=\sum_{i=1}^{n}\sum_{d|i}1*\varphi (d)-\sum_{k=2}^{n}S(\left \lfloor \frac{n}{k} \right \rfloor)=\frac{n(n+1)}{2}-\sum_{k=2}^{n}S(\left \lfloor \frac{n}{k} \right \rfloor)$。

OK丟去篩吧。

#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
//#include<assert.h>
#include<algorithm> 
//#include<iostream>
//#include<bitset>
using namespace std;

#define LL long long
LL n,m;
#define maxn 5000011
const int mod=1e9+7;
int phi[maxn],sumphi[maxn],prime[maxn/10],lp; bool notprime[maxn];
void pre(int n)
{
    lp=0; phi[1]=1; sumphi[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!notprime[i]) {prime[++lp]=i; phi[i]=i-1;}
        sumphi[i]=sumphi[i-1]+phi[i];
        sumphi[i]-=sumphi[i]>=mod?mod:0;
        for (int j=1,tmp;j<=lp && 1ll*prime[j]*i<=n;j++)
        {
            notprime[tmp=i*prime[j]]=1;
            if (i%prime[j]) phi[tmp]=1ll*phi[i]*(prime[j]-1)%mod;
            else {phi[tmp]=1ll*phi[i]*prime[j]%mod; break;}
        }
    }
}

struct Edge{LL to; int v,next;};
#define maxh 1000007
struct Hash
{
    int first[maxh],le;Edge edge[maxn];
    Hash() {le=2;}
    void insert(LL y,int v)
    {int x=y%maxh; Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;}
    int find(LL y)
    {
        int x=y%maxh;
        for (int i=first[x];i;i=edge[i].next) if (edge[i].to==y) return edge[i].v;
        return -1;
    }
}h;

int du(LL n)
{
    if (n<=m) return sumphi[n];
    int tmp=h.find(n); if (tmp!=-1) return tmp;
    LL tot=0;
    for (LL i=2,last;i<=n;i=last+1)
    {
        last=n/(n/i);
        tot+=(last-i+1)*du(n/i)%mod;
        tot-=tot>=mod?mod:0;
    }
    LL ans=(n%mod)*((n+1)%mod)%mod*((mod+1)>>1)%mod-tot;
    ans+=ans<0?mod:0;
    h.insert(n,ans);
    return ans;
}

int main()
{
    scanf("%lld",&n);
    m=(LL)pow(pow(n,1.0/3),2); pre(m);
    printf("%d\n",du(n));
    return 0;
}

?