对于约数个数上界的估计-白红宇

对于约数个数上界的估计

阅读量：5819 次

发布时间：2019-06-18

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

简介

经常遇到一些复杂度与约数个数 \(\text d(n)\) 相关的题, 但是并不保证复杂度, 而且也没见到很好的估计(可能是我菜)...

所以打表算了一下, 下面是结果.

\(\le 10^5\) 的数中 \(d(n)\) 最大的出现在 \(83160 = 2^3 \cdot 3^3 \cdot 5 \cdot 7 \cdot 11\) , \(\text d(83160) = 128\);

\(\le 10^6\) 的数中 \(d(n)\) 最大的出现在 \(720720 = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13\) , \(\text d(720720) = 240\);

\(\le 10^7\) 的数中 \(d(n)\) 最大的出现在 \(8648640 = 2^6 \cdot 3^3 \cdot 5 \cdot 7 \cdot 11 \cdot 13\) , \(\text d(8648640) = 448\);

\(\le 10^8\) 的数中 \(d(n)\) 最大的出现在 \(73513440 = 2^5 \cdot 3^3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17\) , \(\text d(73513440) = 768\).

看起来是根号级别的...似乎是一个介于 \(\sqrt[3]{n}\) 到 \(\sqrt n\) 的一个函数.

在常见的数据范围中, 可以看做 \(\text d(n) \le 500\) 或 \(\text d(n) \le 1000\).

Upd: 似乎看到一个证明: .

上面的paper利用放缩法证明了以下结论：

对于任意正整数 \(n\), 有 \(\text d(n) \le \sqrt{3n}\);

对于 \(n > 1260\), 有 \(\text d(n) < \sqrt{n}\).

Upd2: 对于 \(10^{18}\) 范围内的数, 约数个数最多约为 \(10^5\).

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;#define rep(i,l,r) for(register int i=(l);i<=(r);++i)#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)#define il inlinetypedef double db;typedef long long ll;//--------------------------------------const int N=1e8+5;bool mark[N];int prim[N],d[N],num[N],res=0,resp;int cnt;void initial(){ cnt=0; d[1]=1; for (int i=2 ; i
           
            res)res=d[i],resp=i; }}int main(){ ios::sync_with_stdio(0),cin.tie(0); initial(); cout<
            
             <<' '<
             
              <<'\n'; return 0;}