杜教筛模板
给$mu$找个函数1，因为$mu * 1=I$，其中I是元函数，I(x)=[x==1]。
那就$sum_{i=1}^{n}sum_{d|i}mu(d)=sum_{k=1}^{n}1sum_{d=1}^{left lfloor frac{n}{k} ight floor}mu(d)=sum_{k=1}^{n}S(left lfloor frac{n}{k} ight floor)$
然后$S(n)=sum_{i=1}^{n}sum_{d|i}mu(d)-sum_{k=2}^{n}S(left lfloor frac{n}{k} ight floor)=1-S(left lfloor frac{n}{k} ight floor)$。
搞定！
1 #include<string.h> 2 #include<stdlib.h> 3 #include<stdio.h> 4 #include<math.h> 5 //#include<assert.h> 6 #include<algorithm> 7 //#include<iostream> 8 //#include<bitset> 9 using namespace std; 10 11 #define LL long long 12 LL n,m; 13 #define maxn 5000011 14 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 1000007 33 struct Hash 34 { 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 ",du(n)-du(left-1)); 67 return 0; 68 }