对于约数个数的估计

简介

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

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

1. \(\le 10^5\) 的数中 \(d(n)\) 最大的出现在 \(83160 = 2^3*3^3*5*7*11\) , \(\text d(83160) = 128\);
2. \(\le 10^6\) 的数中 \(d(n)\) 最大的出现在 \(720720 = 2^4*3^2*5*7*11*13\) , \(\text d(720720) = 240\);
3. \(\le 10^7\) 的数中 \(d(n)\) 最大的出现在 \(8648640 = 2^6*3^3*5*7*11*13\) , \(\text d(8648640) = 448\);
4. \(\le 10^8\) 的数中 \(d(n)\) 最大的出现在 \(73513440 = 2^5*3^3*5*7*11*13*17\) , \(\text d(73513440) = 768\).

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

代码

#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