锐客网

  1. 首页 > it技术 > >

杜教筛|[学习笔记] 杜教筛 (51nod 1244+1227 +1237 +1238+1239) - 数论

数论杜教筛

很好的入门讲解
51nod1244和51nod1239是求mu和求phi，略

//get mu #include #include #include #include #include #define N 6366666 #define lint long long #define debug(x) cerr<<#x<<"="< sav; bool np[N]; lint ps[N]; int pri[N],f[N],fs[N]; inline int prelude(int n) { f[1]=fs[1]=1; for(int i=2,c=0,x; i<=n; ++i) { if(!np[i]) pri[++c]=i,f[i]=-1; fs[i]=fs[i-1]+f[i]; for(int j=1; j<=c&&(lint)i*pri[j]<=n; ++j) { x=i*pri[j],np[x]=true; if(i%pri[j]) f[x]=-f[i]; else { f[x]=0; break; } } } return 0; } inline lint G(lint n) { return 1+n-n; } lint F(lint n) { if(sav.count(n)) return sav[n]; if(n

//get phi #include #include #include #include #include #define N 6000000 #define lint long long #define debug(x) cerr<<#x<<"="< sav; bool np[N]; lint ps[N]; int pri[N],f[N],fs[N]; inline int prelude(int n) { fs[1]=f[1]=1; for(int i=2,c=0,x; i<=n; ++i) { if(!np[i]) pri[++c]=i,f[i]=i-1; fs[i]=fs[i-1]+f[i],fs[i]%=mod; for(int j=1; j<=c&&(lint)i*pri[j]<=n; ++j) { x=i*pri[j],np[x]=true; if(i%pri[j]) f[x]=f[i]*f[pri[j]]; else { f[x]=f[i]*pri[j]; break; } } } return 0; } inline lint G(lint n) { return n*inv2%mod*(n+1)%mod; } int F(lint n) { if(sav.count(n)) return sav[n]; if(n

【杜教筛|[学习笔记] 杜教筛 (51nod 1244+1227 +1237 +1238+1239) - 数论】51nod1227那个链接也有讲，然后有两个技巧分别是，小于等于n的和n互质的数字的和，等于(n*phi(n)+[n==1])/2；以及杜教筛的时候并不对d*phi(d)做替换，而只对phi(d)做替换。
#include #include #include #include #include #define N 6000000 #define lint long long #define debug(x) cerr<<#x<<"="< sav; bool np[N]; int pri[N],f[N],fs[N]; inline int mol(lint x) { return x%=mod,x<0?x+mod:x; } inline int prelude(int n) { fs[1]=f[1]=1; for(int i=2,c=0,x; i<=n; ++i) { if(!np[i]) pri[++c]=i,f[i]=i-1; fs[i]=(fs[i-1]+(lint)f[i]*i)%mod; for(int j=1; j<=c&&(lint)i*pri[j]<=n; ++j) { x=i*pri[j],np[x]=true; if(i%pri[j]) f[x]=f[i]*f[pri[j]]; else { f[x]=f[i]*pri[j]; break; } } } //for(int i=1; i<=30; i++) debug(i)sp,debug(f[i])ln; return 0; } inline int G(int n) { return n*(n+1ll)%mod*(2*n+1ll)%mod*inv6%mod; } inline int H(int a,int b){return (a+b)*(b-a+1ll)%mod*inv2%mod; } int F(int n) { if(n

51nod 1237注意到i和j都是到n的，不要用莫比乌斯函数作反演而直接上phi会比较方便。
#include #include #include #include #include #include #define A(x) assert(x>=0) #define N 6000000 #define lint long long #define debug(x) cerr<<#x<<"="< sav; bool np[N]; int pri[N],f[N],fs[N]; inline int mol(lint x) { return x%=mod,x<0?x+mod:x; } inline int prelude(int n) { fs[1]=f[1]=1; for(int i=2,c=0,x; i<=n; ++i) { if(!np[i]) pri[++c]=i,f[i]=i-1; fs[i]=(fs[i-1]+f[i])%mod; for(int j=1; j<=c&&(lint)i*pri[j]<=n; ++j) { x=i*pri[j],np[x]=true; if(i%pri[j]) f[x]=f[i]*f[pri[j]]; else { f[x]=f[i]*pri[j]; break; } } } //for(int i=1; i<=30; i++) debug(i)sp,debug(f[i])ln; return 0; } inline int H(lint a,lint b) { return (a+b)%mod*(b-a+1)%mod*inv2%mod; } inline int G(lint n) { return H(1ll,n); } int F(lint n) { if(n

51nod 1238几乎和51nod1227一模一样，略。
#include #include #include #include #include #include #define A(x) assert(x>=0) #define N 6000000 #define lint long long #define debug(x) cerr<<#x<<"="< sav; bool np[N]; int pri[N],f[N],fs[N]; inline int mol(lint x) { return x%=mod,x<0?x+mod:x; } inline int prelude(int n) { fs[1]=f[1]=1; for(int i=2,c=0,x; i<=n; ++i) { if(!np[i]) pri[++c]=i,f[i]=i-1; fs[i]=(fs[i-1]+(lint)f[i]*i%mod*i)%mod; for(int j=1; j<=c&&(lint)i*pri[j]<=n; ++j) { x=i*pri[j],np[x]=true; if(i%pri[j]) f[x]=f[i]*f[pri[j]]; else { f[x]=f[i]*pri[j]; break; } } } //for(int i=1; i<=30; i++) debug(i)sp,debug(f[i])ln; return 0; } inline int F(lint a,lint b) { return (a+b)%mod*(b-a+1)%mod*inv2%mod; } inline int G(lint n) { return n%=mod,n*(n+1)%mod*(2*n+1)%mod*inv6%mod; } inline int G(lint a,lint b) { return mol(G(b)-G(a-1)); } inline int H(lint n) { return (lint)F(1,n)*F(1,n)%mod; } inline int H(lint a,lint b) { return mol(H(b)-H(a-1)); } int S(lint n) { if(n

    推荐阅读


    上一篇：Vasya and Petya's Game

    下一篇：Android APP开屏界面倒计时圆圈的实现