反质数

问题描述

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。

如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。

现在给定一个数N，你能求出不超过N的最大的反质数么？

分析

这道试题的数学性质很强，关键点在于“一个数与其约数”的关系。在设计算法之前，我们不妨先对“一个数与其约数”进行一番简单的分析。

先举个简单的例子，求一个数756的约数总个数。

大家都知道先将756分解质因子，得到756=22×33×71，再把三个指数加一连乘就是756约数的总个数[1]：(2+1)×(3+1)×(1+1)=24。

在本题中，所要求的是[1,N]范围内最大的反质数，实际上也就是要求约数个数最多的那个数[2]。那么，一个数最多会有多少个不同的质因子呢？最多又会有多少个约数呢？

粗略估算：2×3×5×7×11×13×17×19×23×29=6469693230>2×109。所以，我们就得到了一个很重要的性质：

性质一：在[1,2×10^9]中，一个数最多有10个不同的质因子。

根据经验，一个正整数N，其约数个数是 级的[3]。因此，我们又可以得到另一个重要性质：

性质二：在[1,2×109]中一个数其约数个数大致也就是10^4~10^5级别[4]。

这两个性质虽然是通过估算得出的，但其正确性是无庸质疑的。在以后的算法设计中，这两个性质将起着举足轻重的作用。

再回头看对正整数756的分析：756=22×33×71­，共有24个约数。那么它是否是一个“反质数”呢？显然，我们可以构造出另一个正整数，也有24个约数，却比756要小：540=22×33×51。

构造反例的原理在于，756的质因子2、3、7不是连续的质数，漏了5，用5代替7，而指数不变就可以构造出一个更小的但有着相同约数个数的正整数。因此，我们又得到了一个关于“反质数”的性质：

性质三：一个反质数的质因子必然是从2开始连续的质数。

分析至此，对“一个数和其约数”，“反质数”我们已有了初步的了解，并且大致掌握了一些基础性质。下面，在这些分析的基础上，我们开始尝试着设计一个时间效率上能够被接受的算法。

由于题目中N的范围很大——有2×109，所以想通过求出每个数约数的个数，最后通过统计找出最大的反质数，这种方法效率很低，是不现实的。我们必须另辟蹊径。

在[1, 2×109]中有很多数显然不是“反质数”，在先前的分析中，性质三就充分说明了这一点。

根据题目对“反质数”的定义，我们知道，不可能有两个反质数，其约数个数相同。那么，根据性质二，“反质数”的个数将远远小于2×109，而只是104到105级别。这样一来，我们就可以考虑直接产生所有的“反质数”，再从中找出最大的。

在先前的题意分析中，我们知道：“反质数”与一个数的约数总数，质因子总数都有着莫大的联系，不妨将这个因素放在一起。

设f(i,j)记录的是：约数总数为i，有j个不同的质因子的最小正整数。

显然，所有的“反质数”都出自f(i,j)。如果能计算出所有f(i,j)，那么只要在其中扫描一遍，就可以得到问题的解了。现在的问题就转化成如何快速求出f(i,j)。

 

还是举个简单例子，假设f(12,3)=60，60=22×31×5。因此，f(6,2)一定为12，若f(6,2)小于12，我们可以用f(6,2)×5来代替原来f(12,3)中60的值。这正是关于f(i,j)的最优化原理——因此，可以用动态规划来求解！

经过上述分析，问题被揭开了神秘的面纱，顺着动态规划线索，我们可以从容的写出以下结论：

 

l 状态表示：

f(i,j)记录“约数总数为i，有j个不同的质因子的最小正整数”。

l 边界条件：

f(1,0)=1

l 状态转移方程：

假设p( j )记录的是第j大的质数。


l 规划方向：

一质因子个数j为阶段进行规划。

 

根据性质二，参数i的范围不超过是10^5，参数j的范围不超过10。所以，算法的空间复杂度还是可以承受的，不超过 。在状态转移中，由于有 ，所以k不会超过log2N，因此，算法的时间复杂度不超过 也是可以被接受的。

 



--------------------------------------------------------------------------------

[1] 用组合数学乘法原理可以证明。

[2] 求[1,N]中最大的反质数就是求[1,N]中约数个数最多的数（如果有约数个数相同，则该数尽量小）。这点可以轻易证明，在此就不赘述了。

[3] 最极限的情况是[1, ]都是N的约数，因此在[ ,N]中也有相应个数的约数存在，总约数个数为2 级别。当然，这种极限情况在N很大时是不可能被达到的。

[4] 这个估算是相当保守的，事实上，只有10^3~10^4级别。