这是有问题的问题： 问题＃78
这真让我抓狂。我已经在这个工作了几个小时了，我已经能够降低查找堆栈方式的复杂性 n 硬币来 O(n/2)，但即使有这些改进 和 从一个开始 n 为此 p(n) 接近一百万，我还是不到一分钟就达不到答案。实际上根本没有。
有什么提示可以帮助我吗？
请记住，我不想要一个完整的解决方案，这里不应该发布任何功能性解决方案，以免破坏其他人的问题。这就是我没有包含任何代码的原因。
这是有问题的问题： 问题＃78
这真让我抓狂。我已经在这个工作了几个小时了，我已经能够降低查找堆栈方式的复杂性 n 硬币来 O(n/2)，但即使有这些改进 和 从一个开始 n 为此 p(n) 接近一百万，我还是不到一分钟就达不到答案。实际上根本没有。
有什么提示可以帮助我吗？
请记住，我不想要一个完整的解决方案，这里不应该发布任何功能性解决方案，以免破坏其他人的问题。这就是我没有包含任何代码的原因。
维基百科 可以帮到你。我假设您已经拥有的解决方案是递归，例如“中间函数”部分中的递归。这可以用来找到欧拉问题的解决方案，但速度不快。
更好的方法是使用基于的递归 五角数定理 在下一节中。这个定理的证明并不是直截了当的，所以我不认为问题的作者希望你自己提出这个定理。相反，它是其中一个问题，他们期望一些文献搜索。
这个问题实际上是要求在整数分区序列中找到可被1,000,000整除的第一项。
整数n的分区是描述正整数之和（n）可以加到一起等于n的方式的一种方式，而不管顺序如何。函数p（n）用于表示n的分区数。下面我们将5个“硬币”显示为评估7个分区的加数，即p（5）= 7。
5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1
我们使用生成函数来创建系列，直到找到所需的n。 生成函数最多需要500个所谓的广义五边形数，由n（3n - 1）/ 2给出，其中0，±1，±2，±3 ......，前几个是0,1,2,5 ，7,12,15,22,26,35 ......（Sloane的A001318）。
我们有以下生成函数，它使用我们的五角数作为指数：
1 - q - q ^ 2 + q ^ 5 + q ^ 7 - q ^ 12 - q ^ 15 + q ^ 22 + q ^ 26 + ...
我的blog.dreamshire.com博客有一个perl程序可以在10秒内解决这个问题。
这里有一些提示：
100万的可分性与仅仅超过一百万的不同是不一样的。 100万= 1,000,000 = 10 ^ 6 = 2 ^ 6 * 5 ^ 6。
所以问题是要找到最低的n，以便p（n）的因子包含6个2和6个5。