在数论里面除了老生常谈的素数问题，还有一个就是约数个数问题。对于这个问题的解法可能还停留在用n除以 $1,\cdots,\sqrt n$，然后统计能够整除的个数。其时间复杂度为 $O(\sqrt n)$。本文主要介绍约数个数定理以及它在实际题目中的应用。

约数个数原理

• 原理
  对于一个大于 1 的正整数 n，n 可以因式分解为 $$ n = \prod _{ i = 1 } ^k p _i ^{ a _i } = p _1 ^{ a _1 } * \cdots * p _k ^{ a _k } $$, 其中$ p _i $是质数，$ a _i \in N $，那么n的约数个数就是 $$ f ( n ) = \prod _{ i = 1 } ^k ( a _i + 1) = ( a _i + 1) * \cdots *( a _k + 1 ) $$

• 简证
  因为 $p_i$ 都是质数，无法再进行因式分解，所以任意 $p_i$ 的组合都可以构成一个约数，对于质数 $p_i$ 有 $(a_i+1)$ 种可能，分别是 $0,1,\cdots,a _i$，那么对于 k 个 $p_i$ 共有 $\prod _{i=1}^k (a _i +1)$ 种可能的组合。

代码实现

• 思路
  要求解一个整数n的约数个数 $f(n)$，其关键就是通过因式分解获取各个质数的指数。不过通常情况下，我们无法获取比n小的质数有哪些（$ 10^{16} $以内的质数有 104165820+ 个，所以数目还是可观的。）这里我们通过n不断除以除数m，$ m \in {2,3,5,7,9,\cdots} $，如果能够整除的话，就更新 n 为$ n/m $，这样虽然除数里面有 9 这样的合数，但经过除以 2 次 3 后，9 将会不被更新后的 n 整除，所以实际的情况还是除以质数。

• c++代码

   1// 快速计算n的约数个数
   2int NumOfFac(long long n){
   3    unsigned int i,k,count=1;
   4    long long m=n;
   5    while(m!=1){
   6        for(i=2; i<=m; i+=2){
   7            if(m % i == 0){
   8                k=1;
   9                while(m % i == 0){
  10                    k++;
  11                    m = m / i;
  12                }
  13            count = count*k;
  14            }
  15        // 2,3,5,7,11...避开2->3之间差1
  16        if(i == 2)
  17            i--;
  18        }
  19    }
  20    return count;
  21}
  

  `

解题报告

• HihoCoder

  1. divisors: divisors | 源码 | 报告细节

     注意点：

     1. 暴力求解(遍历比n小的数，依次求解每个数的约数个数)是行不通的。

     2. 合理利用约数个数原理，并对其进行优化求解。

        TIPS:
        最终求解的拥有最大约数个数的数一定满足下面的推论：
        若$p _1 < p _2 < \cdots < p _k$,则$a _1 > a _2 > \cdots > a _k$