[牛客] n的约数唯一分解定理+dfs-白红宇

[牛客] n的约数唯一分解定理+dfs

阅读量：327 次

发布时间：2019-03-04

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

题目链接：

题意

t次询问，每次给你一个数n，求在[1,n]内约数个数最多的数的约数个数。 (n≤ ${10^{18}}$ )

题解

我们先来分析这道题，首先我们知道每个数都可以分解成质因数乘积的形式。

{num=p1^{k_1}*p_2^{k_2}*...*p_m^{k_m}}

（

{p_1,p_2....p_m}

为num的质因数）

那么很容易我们可以得到一个数的约数个数为： ${(k_1+1)*(k_2+1)*...*(k_m+1)}$

那么要找1~n里约数最多的，肯定是分解成质因数后个数最多的。

我们打表可以发现前15个质数相乘就达到极限，再多乘一个最小质因数2就会超出

{10^{18}}

的范围。可能有人会问为什么只是前15个，后面还有很多数的质因数没在这15个质数里面，注意我们要找的是约数个数最多的，所以质因数个数应该尽可能多，质因数个数要尽可能多，那么质因数应该尽可能小。

我们只需枚举这15个质数，然后再枚举每个质数的个数即可。可以用dfs来求解

我dfs的参数有当前数的大小，当前枚举到第几个质数，当前质数个数的上限，当前数的约数个数。

一开始我没有加上“当前质数个数的上限”参数，结果我超时了。因为一开始为2时的上限是64 （ ${2^{64}}>10^{18}$ ），所以我全部设的上限为64，很明显 ${64^{15}}$ 必超时。所以必须加上“当前质数个数的上限”参数，很明显为了得到约数个数尽可能多，那么质数越小的时候个数应该尽可能多，所以每搜索到下一个质数的个数一定小于当前质数个数。

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     using namespace std;//extern "C"{void *__dso_handle=0;}typedef long long ll;typedef long double ld;#define fi first#define se second#define pb push_back#define mp make_pair#define pii pair
                     
                      #define lowbit(x) x&-xconst double PI=acos(-1.0);const double eps=1e-6;const ll mod=1e9+7;const int inf=0x3f3f3f3f;const int maxn=1e5+10;const int maxm=100+10;#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int p[20];ll n;void getprime(){ p[0]=0; int cnt=1; for(int i=2;cnt<=15;i++) { bool flag=true; for(int j=2;j<=sqrt(i);j++) if(i%j==0) { flag=false; break;} if(flag) p[cnt++]=i; }}ll dfs(ll num,int pos,int lim,ll ans){ ll tmp=ans; if(pos>15) return ans; for(int i=1;i<=lim;i++) { if(n/p[pos]

转载地址：http://vmmh.baihongyu.com/

你可能感兴趣的文章