51nod1244 莫比乌斯函数之和
杜教筛模板
给$\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 #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\n",du(n)-du(left-1)); 67 return 0; 68 }View Code 优质内容筛选与推荐>>
1、IDE-IntelliJ IDEA 主题、字体、编辑区主题、文件编码修改、乱码问题
2、CSS3 Transition
3、Linux内存管理（text、rodata、data、bss、stack&heap）
4、[development][dpdk][pktgen] 网卡收发包性能测试
5、HTML基础2