cpper编程论坛 - 查看单个帖子

Elminster · #3 (**permalink**) 2008-05-20

引用:

作者: polyrandom

给定任意大于等于8的整数I，求指数数列x1, x2, ..., xn，使得x1 + x2 + ... + xn等于I，并且x1, x2, ..., xn两两不同。并且，如果有多个这样的数列满足这一条件，那么，要求出这些数列中n最大的那个。

其实算法不难的，问题是我想出的算法复杂度太高了，有没有低一点的？

复杂度太高是多高？这个问题可以看作整数背包问题的一个变种，有 O(I*k) 的算法，这里 k 是所有小于 I 的整数的素数个数。你要更低的话，怕是难了。