你说对了，输入n是奇数的话，所要求结果正好等于2^(n-1)

有趣！大家注意审题！
战斗力为n时，最小的部队数是多少?
得到最小部队时，也许战斗力大于n
所以，我的理解是：
    战斗力为大于等于n时，最小的部队数是多少?

呵呵，各位的讨论有点意思，题目不难，但也没各位想的那么简单。

题目的理论基础是数论和组合数学，具体点就是算术基本定理和排列组合。

纠正前面两位的一处错误，并非当n为奇数时结果是2^(n-1)，而是当n为质数时结果才为2^(n-1)。我估计各位只观察了3,5,7的结果而已。

举个反例，当n=9时，2^(9-1) = 256，而实际应该是36 （1、2、3、4、6、9、12、18、36）。

再给点提示 36 = (2^2)*(3^2)，注意指数与n的关系。

最后再纠正楼上理解的错处，不是大于等于，只是等于。

各位再接再厉。


[ 本帖最后由 beyondyf 于 2012-8-28 21:38 编辑 ]

杨大哥已经提醒的差不多了。我详细说说我的思路，应该和杨大哥想的一样。

任何一个数最终能分解成：p1^r1 * p2^r2 ... ps^rs 的形式，其中 pi 都是素数，且这种分解形式是唯一的(这个结论就是杨大哥说的算术的基本定理)。这个过程称为素因数分解。比如 36 = 2^2 * 3^2。
那么 36 的全部约数能从这个形式中求出。2 这个因数能用 0次，1次，2次，3这个因数也能用0次，1次，2次，搭配起来能凑出 3*3 = 9 个组合，都是 36 的约数。比如 2 用 0 次配 3 用 0 次，就是 2^0 * 3^0 = 1。是 36 的一个约数。
一般地，对于任何数的分解形式：p1^r1 * p2^r2 ... ps^rs 一共就有 (r1+1)(r2+1)...(rs+1) 个约数。

现在反这想这个问题，如果我想要一个有 9 个因数的数，那么我需要一个式子 (r1+1)(r2+1)...(rs+1) = 9 才行。
杨大哥给了个结论，是如果 n 是质数的话，它就不可能能分解成几个数的乘积于是只能是 r1+1 = n，任意质数 p^(n-1) 都满足只有 n 个约数的条件，当然为了尽量小，要取 p ＝ 2。
对于 9 的话，可以是 8+1 = 9, (2+1)(2+1) = 9，所以即可能是 2^8，也可以是 2^2 * 3^2。这里得找个小的。因为 2^8 可以看成 2^2 * 2^6， 所以这里就是要决断 2^6 和 3^2 谁大的问题。

这里我还没有太想好代码应该怎样处理。主要是判断如何拆分这个 n，以使得最后得的乘积尽量小。不过思路肯定是这样下去的。


[ 本帖最后由 pangding 于 2012-8-28 22:28 编辑 ]

我还在对这个题的理解上琢磨。
举例：
部队数为16时，结合有：1  2  4  8 16,即战斗力为5
部队数为12时，组合有：1  2  3  4  6  12，即战斗力为6

战斗力为6，不包含5吗？



[ 本帖最后由 netlin 于 2012-8-29 09:18 编辑 ]

的确按照杨大哥的思路下去却实能简便很多
可以把输入的n拆分成几个最简质因数相乘的形式 比如24=2*2*2*3
但是如何组合几个 因数 但是直接用这几个数能组合出来的最小数是   2^2*3*5*7=420
          然而    把因子中得2*2组合成4的话      2^3*3^2*5=360
如果一个数很大能拆分成很多个质因数 而且其中2,3的数量比较多的话 组合的数量就会更多
这个问题 今天想了一天 也没想出什么方法去处理

你这个可以当成另一道题，也挺有意思的。
ACM的题，一般搞个背景主要是为了提高些乐趣，不一定都很合理。比如 12 就能达到 6 的战斗力话，组 16 个人只有 5 的战斗力就有点不划算。但就题论题，我觉得还是我们的理解。

我也是卡的这。今天比较忙没怎么想，不过感觉是没什么思路。

解释问题表述为下，题目主要是找出能被一个数N 整除的个数 即为因子个数   问题求解点是知道 因子个数M 求这个N 是多少 并找出最小的N

呵呵 弄不来
  
   




[ 本帖最后由 zhu224039 于 2012-8-30 06:52 编辑 ]