对于约数个数上界的估计

简介

经常遇到一些复杂度与约数个数 \(\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
#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 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 ; ires)res=d[i],resp=i;
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    initial();
    cout<
积性函数

相关

利用powerful number求积性函数前缀和

【数学】加性函数与积性函数

积性函数学习笔记

标签