【题目链接】 

 

【题目大意】

　　计算莫比乌斯函数的区段和

 

【题解】

　　利用杜教筛：

　　求F(n)=∑(f(i))

　　存在g=f*I，定义G(n)=∑(g(i))

　　就可以得到F(n)=G(n)-∑(F(n/i))

　　加一些预处理我们可以做到O(n^(2/3))求解F(n)

　　我们知道积性函数∑(miu(d))=0(d|n)，又有∑(miu(d))=1(n=1)，

　　所以∑∑(miu(d))=1(d|i){i=1}^{n},

　　因此我们得到F(n)=1-∑F(n/d){d=2}^{n}

　　同时用Hash记忆化miu函数的前缀和

 

【代码】

#include 
     
      #include 
      
       using namespace std;const int mod=1333331;typedef long long LL;LL a,b,miu[5000010];int p[500010],cnt=0;bool vis[5000010];struct HASHMAP{    int h[mod+10],cnt,nxt[100010];    LL st[100010],S[100010];    void push(LL k,LL v){        int key=k%mod;        for(int i=h[key];i;i=nxt[i]){            if(S[i]==k)return;        }++cnt;nxt[cnt]=h[key];h[key]=cnt;        S[cnt]=k;st[cnt]=v;    }    LL ask(LL k){        int key=k%mod;        for(int i=h[key];i;i=nxt[i]){            if(S[i]==k)return st[i];        }return -1;    }}H;void Get_Prime(){    miu[1]=1;    for(int i=2;i<=5000000;++i){        if(!vis[i]){p[++cnt]=i;miu[i]=-1;}        for(int j=1;j<=cnt;++j){            if(1LL*p[j]*i>5000000)break;            int ip=i*p[j];            vis[ip]=true;            if(i%p[j]==0)break;            miu[ip]=-miu[i];        }    }for(int i=2;i<=5000000;++i)miu[i]+=miu[i-1];}LL miu_sum(LL n){    if(n<=5000000)return miu[n];    LL tmp=H.ask(n),la,A=1;    if(tmp!=-1)return tmp;    for(LL i=2;i<=n;i=la+1){        LL now=n/i; la=n/now;        A=A-(la-i+1)*miu_sum(n/i);    }H.push(n,A);return A;}int main(){    scanf("%lld%lld",&a,&b);    Get_Prime();    printf("%lld\n",miu_sum(b)-miu_sum(a-1));    return 0;}