杜教筛模板
给$\mu$找个函数1，因为$\mu * 1=I$，其中I是元函数，I(x)=[x==1]。
那就$\sum_{i=1}^{n}\sum_{d|i}\mu(d)=\sum_{k=1}^{n}1\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\mu(d)=\sum_{k=1}^{n}S(\left \lfloor \frac{n}{k} \right \rfloor)$
然后$S(n)=\sum_{i=1}^{n}\sum_{d|i}\mu(d)-\sum_{k=2}^{n}S(\left \lfloor \frac{n}{k} \right \rfloor)=1-S(\left \lfloor \frac{n}{k} \right \rfloor)$。
搞定！
1 #include2 #include 3 #include 4 #include 5 //#include 6 #include 7 //#include 8 //#include 9 using namespace std;10 11 #define LL long long12 LL n,m;13 #define maxn 500001114 int miu[maxn],summiu[maxn],prime[maxn/10],lp; bool notprime[maxn];15 void pre(int n)16 {17 lp=0; miu[1]=1; summiu[1]=1;18 for (int i=2;i<=n;i++)19 {20 if (!notprime[i]) {prime[++lp]=i; miu[i]=-1;}21 summiu[i]=summiu[i-1]+miu[i];22 for (int j=1,tmp;j<=lp && 1ll*prime[j]*i<=n;j++)23 {24 notprime[tmp=i*prime[j]]=1;25 if (i%prime[j]) miu[tmp]=-miu[i];26 else {miu[tmp]=0; break;}27 }28 }29 }30 31 struct Edge{LL to; int v,next;};32 #define maxh 100000733 struct Hash34 {35 int first[maxh],le;Edge edge[maxn];36 Hash() {le=2;}37 void insert(LL y,int v)38 { int x=y%maxh; Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;}39 int find(LL y)40 {41 int x=y%maxh;42 for (int i=first[x];i;i=edge[i].next) if (edge[i].to==y) return edge[i].v;43 return -1;44 }45 }h;46 47 int du(LL n)48 {49 if (n<=m) return summiu[n];50 int tmp=h.find(n); if (tmp!=-1) return tmp;51 LL tot=0;52 for (LL i=2,last;i<=n;i=last+1)53 {54 last=n/(n/i);55 tot+=(last-i+1)*du(n/i);56 }57 LL ans=1-tot;58 h.insert(n,ans);59 return ans;60 }61 62 int main()63 {64 LL left;scanf("%lld%lld",&left,&n);65 m=(LL)pow(pow(n,1.0/3),2); pre(m);66 printf("%d\n",du(n)-du(left-1));67 return 0;68 }