二 03
本题关键在于挖掘“反质数”的隐含意义，如果一个数X是反质数，则它的约数的个数大于所有Y(X>Y)的约数的个数。根据定义我们可以看出， 在一个具有相同约数个数的正整数集合中，最小的正整数是反质数。例如约数个数为6的正整数集合{12,18,45,75,175…}，只有12是反质 数。因为任何一个比12大且约数个数等于6的数，都不满足反质数定义。所以，寻找不大于N的最大反质数问题可以转化成，寻找不大于N的约数个数最多的最小 正整数。
求一个数的约数个数可以用乘法原理，例如75=3^1*5^2，则75有(1+1)*(2+1)=6个约数。对于这道题我们可以采取搜索的方法。按照质因数从小到大依次枚举指数，找出最多的约数个数情况下最小的正整数。
Read the rest of this entry »
Recent Comments