对于约数个数上界的估计

﹏ヽ暗。殇╰゛Y 2022-01-08 00:41 212阅读 0赞

## 简介 ##

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

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

1.  \\(\\le 10^5\\) 的数中 \\(d(n)\\) 最大的出现在 \\(83160 = 2^3 \\cdot 3^3 \\cdot 5 \\cdot 7 \\cdot 11\\) , \\(\\text d(83160) = 128\\);
2.  \\(\\le 10^6\\) 的数中 \\(d(n)\\) 最大的出现在 \\(720720 = 2^4 \\cdot 3^2 \\cdot 5 \\cdot 7 \\cdot 11 \\cdot 13\\) , \\(\\text d(720720) = 240\\);
3.  \\(\\le 10^7\\) 的数中 \\(d(n)\\) 最大的出现在 \\(8648640 = 2^6 \\cdot 3^3 \\cdot 5 \\cdot 7 \\cdot 11 \\cdot 13\\) , \\(\\text d(8648640) = 448\\);
4.  \\(\\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<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<set>
    #include<map>
    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 inline
    typedef 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<N ; ++i)
        {
            if (!mark[i])
            {
                prim[cnt++]=i;
                num[i]=1;
                d[i]=2;
            }
            for (int j=0 ; j<cnt && i*prim[j]<N ; ++j)
            {
                mark[i*prim[j]]=1;
                if (!(i%prim[j]))
                {
                    num[i*prim[j]]=num[i]+1;
                    d[i*prim[j]]=d[i]/(num[i]+1)*(num[i*prim[j]]+1);
                    break;
                }
                d[i*prim[j]]=d[i]*d[prim[j]];
                num[i*prim[j]]=1;
            }
            if(d[i]>res)res=d[i],resp=i;
        }
    }
    
    int main(){
        ios::sync_with_stdio(0),cin.tie(0);
        initial();
        cout<<res<<' '<<resp<<'\n';
        return 0;
    }

转载于:https://www.cnblogs.com/ubospica/p/10392523.html

[-]: https://wenku.baidu.com/view/9e336795bb4cf7ec4afed057.html