本题的解法是在 基本算法之约数个数原理 的基础上对问题进行优化，从而大大降低算法的时间复杂度。而解题的思路是从结果去想它满足什么样的条件，从而获得优化问题的方法。
题目
题目来自微软2016年校招探星夏令营第二题 Divisor，并在 HiHoCoder上进行编程笔试，题目大意是：
给一个数n，$n < 10^{16}$，输出在$1 \sim n$之间约数最多的数，如果有多个相同最大约数个数的数，就输出最小的数
思路
暴力求解
根据 基本算法之约数个数原理，我们可以很快的计算出给定的数 n 的约数个数。不过显然其时间复杂度是很大的。提交的结果是超时。枚举优化
假定 n 以内的所有质数为 $ p _1, \cdots , p _k $,那么对于 n 有 $$ n = \prod _{i=1}^k p _i^{a _i} = p _1^{a _1} * \cdots * p _k^{a _k}
$$ , 其中 $ a _i \in [ 0, \lfloor \log _{p _i} n \rfloor ] $ ，这个就是约数个数原理。通过对这 k 个 $ a _i $ 的自由组合我们能够枚举 n 以内所有的数。 而本题要求的是正整数n的约数个数最多并且 n 尽量小。该目的就是我们优化或剪枝 $ a _i $ 组合的出发点。约数个数最多
对于正整数n的约数个数 $ f(n)= \prod _{i=1}^k (a _i+1) $ ,而要使 $ f(n)$ 更大，那么 $a _i$ 值要大并且 $ a _i == 0 $ 的数目要少，这样乘积才会更大，当然此时 n 也会更大，这里 $ a _i $ 是质数 $ p _i $ 的指数。这里的冲突点在于当要给某个 $ a _i $ 增加值时，是给小的 $p _i$ 增加个大值还是给大的 $p _i$ 增加个小值。简单的例子如下：对于4这个整数，乘上 19 和 2^4 得到的 $f(76)=6,f(64)=7$ ，而对于 8 这个整数，乘上 19 和 2^4 得到的 $f(152)=8,f(128)=8$ ，再对于 16 这个整数，乘上 19 和 2^4 得到的 $f(304)=10,f(256)=9$。该冲突让我们考虑到底要用哪些 $p _i$ 来构成这个约数个数最多的数。经过计算质数 $[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]$ 依次相乘为 $1.3 \times 10^{16}$。显然对于正整数 $N < 10^{16}$ 以内约数个数最多的数 n 一定是由上面的 14 个质数组成。剪枝条件1：
对于正整数 $N < 10^{16}$ 以内约数个数最多的数 n 一定是由这 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43] 14个质数组成。简要证明
假设最终的 n 中有约数大于 43 的质数 $p _k$，其中 $n<N$ ,那么上面的质数组里必定有一个质数 $p _j$ 的指数为 0,不然n一定会超出 N。那么此时用 $p _j$ 代替 $p _k$ 一定会获得比 n 更小的值 $n'$，那么n并不是最终的 n，这和假设矛盾。n 尽量小
当约数个数相同的时候，会取 n 最小的那个正整数。这也就意味着此时 k 个 $a _i$ 的取值已经确定了，但是每个 $a _i$ 对应的质数 $p _j$ 还没有确定（ $i,j \in [0,k]$ ），不同的组合会构成不同的数，但是最小的正整数只能有一种组合，那就是最大的 $a _i$ 对应最小的 $p _j$。所以我们获得了另一个剪枝的条件。剪枝条件2：
最终求解的拥有最大约数个数的数 n 一定满足：
若 $p _1 < p _2 < \cdots < p _k$，则$a _1 > a _2 > \cdots > a _k$。
算法说明
剪枝条件 1 的应用
定义静态常量数组，用来存放这 14 个质数1static const int little_prime[] = { 22,3,5,7,11,13,17,19,23,29, 331,37,41,43};递归函数的声明
函数功能是当第 len 位质数加入后，寻找约数个数最多的最小正整数 ，其参数如下:- N – 输入要寻找的 N 范围内
- n – 求解的 n
- counts – 约数的个数
- len – 第 len 个质数
- maxTimes – 第 len 个质数的最大指数
1void FindMinN(long long N, long long n, int counts, int len, int maxTimes);函数内部解析
- numOfMinN – 全局变量，用来存储当前所找数中约数最多的值
- minN – 全局变量，用来存储当前所有数中最小的n
1// 当第len位质数加入后，寻找约数个数最多的最小正整数 2void FindMinN(long long N, long long n, int counts, int len, int maxTimes){ 3 // 当找到约数个数更多或者约数个数相同但数更小的直接更新 4 // update 5 if(counts > numOfMinN || (counts == numOfMinN && minN > N)){ 6 numOfMinN = counts; 7 minN = n; 8 } 9 10 // find 11 int i; 12 // 遍历第len位质数，其指数为1,2，。。。，maxTimes 13 for(i=1; i<=maxTimes; i++){ 14 n = n * little_prime[len]; 15 if(ans > N) 16 break; 17 // 遍历第len+1位质数，其指数的最大值为i -- 剪枝条件2 18 FindMinN(N, n, counts*(i+1), len+1, i); 19 } 20}
举一反三
k维数组的遍历
对本题的另一种解读是n维数组的遍历。这里每个$p _i$算一个维度，在每个维度上有$a _i+1$个可能的值。对这k个维度的遍历就是对比N小的正整数的依次判别。代码说明
1// 每个维度取值个数 2int varMax[]={ 310,9,8,7,6, 45,4,3,2,1}; 5// 第ind维度取值的情况 6void TraversalByRecu(int dim, int ind, int max, int var[]){ 7 // 取完dim个维度打印输出 8 if(ind>=dim){ 9 for(int j=0; j<dim; j++){ 10 printf("%d\t",var[j]); 11 } 12 printf("\n"); 13 return; 14 } 15 int i; 16 // 第ind维度取完所有可能的取值 17 for(i=1;i<=max;i++){ 18 var[ind]=i; 19 // 取第ind+1维度，并设定第ind+1维度取值个数 20 TraversalByRecu(dim,ind+1,varMax[ind+1],var); 21 } 22}`
区间里约数个数最大的尽量小的数 对于这个问题，其实和N以内很类似，唯一的区别可能就是在更新的时候要判断当前的 n 在不在区间范围内。
代码说明
1void FindMinN(long long low, long long high, long long n, int counts, int len, int maxTimes){ 2 // update 3 if(n<=high && n>=low){ 4 if(counts > numOfMinN || (counts == numOfMinN && minN > n)){ 5 numOfMinN = counts; 6 minN = n; 7 } 8 } 9 // find 10 int i; 11 for(i=1; i<=maxTimes; i++){ 12 n = n * little_prime[len]; 13 if(n > high) 14 break; 15 FindMinN(low, high, n, counts*(i+1), len+1, i); 16 } 17}`
