最小质因数和-白红宇

最小质因数和

阅读量：5360 次

发布时间：2019-06-15

本文共 1725 字，大约阅读时间需要 5 分钟。

这题实在是比较一棵赛艇就发上来好了。

题目：

给定n，求出小于等于n的所有合数的最小质因数之和。

对于70%的数据，n<=10^7。

对于100%的数据，n<=10^9。

题解：

70% 线筛大法好

100%

首先我们考虑对于每一个小于等于sqrt(n)的质数容斥，然后稍微推一推就可以得到一个比较靠谱的容斥方法，虽然复杂度玄学但是似乎跑得蛮快的。然后我们测一下时间……真是不巧n=10^9要跑2s左右。（我就是这么被卡掉的

标程是这样的：

我们定一个阀值k=100，对于<=k的质因数（一共也就才几十个）我们用科学的容斥搞一搞，这个复杂度基本没有。

对于>=k的质因数p我们可以发现n/p是在10^7以内的。然后为了保证质因数是最小的，我们必须只能选n不是<p质数的倍数的。那么我们发现n/p显然也要不是<p质数的倍数。

这样我们用一个暴力筛法来维护n/p，具体做法是因为p递增时n/p递减，那么我们考虑线筛的上界也是递减的，每次线筛赋值bool数组的时候顺便更新一下答案，减小上界的时候就把多的答案扣掉。既然1kw的暴力筛法可以过，这样显然是科学的。

n=10^9只要跑0.1s左右。事实上如果把k设成1000跑n=10^10也只要跑0.6s左右。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               using namespace std;int sq,n;#define FJ 100 //1000?#define ZS 10000005bool yz[ZS+3];int mn=ZS,cnt=0;bool isprime(int x){ for(int p=2;p*p<=x;p++) { if(x%p==0) return 0; } return 1;}int pn=0,ps[233333];long long ans=0;void dfs(int x,int lst,int dep){ if(lst!=0) { ans+=n/x*(long long)ps[lst]*dep; if(x==ps[lst]) ans-=x; } for(int i=lst+1;i<=pn;i++) { if(ps[i]<=FJ&&(long long)x*ps[i]<=n) dfs(x*ps[i],i,-dep); else break; }}void xj(int p){ while(mn>p) cnt-=yz[mn--];}void pj(int p){ for(int j=p;j<=mn;j+=p) { if(yz[j]) continue; yz[j]=1; ++cnt; }}#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}int main(){ //FO(prime) scanf("%d",&n); sq=sqrt(n)+1; int cc=0; for(int i=2;i<=sq;i++) { if(isprime(i)) ps[++pn]=i; } dfs(1,0,-1); for(int i=1;i<=pn;i++) { int cur=ps[i]; if(cur>FJ) { xj(n/cur); ans+=(n/cur-cnt-1)*(long long)cur; } pj(cur); } printf("%lld\n",ans);}

嗯今天闫神还立了一个flag，说不会求质数的答案。那我们就是要求n以内质数的和。

丢链接跑

转载于:https://www.cnblogs.com/zzqsblog/p/5399730.html

你可能感兴趣的文章