[51nod]1244 莫比乌斯函数之和

题目大意：求[a,b]之间内的莫比乌斯函数μ之和。（$a,b<=10^{10}$）

思路：令$ M(n)=sum_{i=1}^{n}mu (i)  $，题目所求即为$ M(b)-M(a-1) $。

由于$ sum_{d|n} mu (d)=left [ n=1 ight ] $ ，所以$ sum_{i=1}^{n} sum_{d|i} mu (d)=1 $

令$ i=kd $，则有$ sum_{i=1}^{n} sum_{d|i} mu (d)= sum_{k=1}^{n} sum_{d=1}^{left lfloor n/k ight floor} mu (d) = sum_{k=1}^{n} M(left lfloor n/k ight floor) =1 $

那么$ M(n)=1-sum_{i=2}^{n} M(left lfloor n/i ight floor) $

由于$ left lfloor n/i ight floor $的取值只有$ O(sqrt{n}) $种，预处理出前$ n^{frac{2}{3}} $的$ M(n) $，然后记忆化搜索，可以证明总时间复杂度为$ O(n^{frac{2}{3}}) $（这个好像被叫做杜教筛）。

#include<iostream>
using namespace std;
#define ll long long
#define MN 6000000
#define MP 413000
#define MOD 5999993
struct edge{int u;ll x;edge*nx;}*h[MOD];
int u[MN+5],p[MP+5],pn;
bool f[MN+5];
int cal(ll x)
{
    if(x<=MN)return u[x];
    for(edge*i=h[x%MOD];i;i=i->nx)if(i->x==x)return i->u;
    edge*np=new edge;*np=(edge){1,x,h[x%MOD]};h[x%MOD]=np;
    for(ll i=2,ls;i<=x;i=ls+1)ls=x/(x/i),np->u-=(ls-i+1)*cal(x/i);
    return np->u;
}
int main()
{
    ll a,b;int i,j;
    cin>>a>>b;
    for(u[1]=1,i=2;i<=MN;++i)
    {
        if(!f[i])p[++pn]=i,u[i]=-1;
        for(j=1;i*p[j]<=MN&&(f[i*p[j]]=1);++j)
            if(i%p[j])u[i*p[j]]=-u[i];else break;
        u[i]+=u[i-1];
    }
    cout<<cal(b)-cal(a-1);
}