Project Euler 78

发表于 更新于 分类于 阅读次数： 本文字数： 710 阅读时长 ≈ 1 分钟

Project Euler 78

题目

Coin partitions

Let \(p(n)\) represent the number of different ways in which \(n\) coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so \(p(5)=7\).

1
2
3
4
5
6
7
OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O

Find the least value of \(n\) for which \(p(n)\) is divisible by one million.

解决方案

本题所使用的的状态转移方程和第76题完全一致。不过，由于本体求的是第一个\(p(n)\)能被\(10^6\)整除，因此需要更快的方法。

将\(p(n)\)的前一些项放进OEIS查询，结果为A000041。

在FORMULA一栏中可以发现以下信息：

1
a(n) - a(n-1) - a(n-2) + a(n-5) + a(n-7) - a(n-12) - a(n-15) + ... = 0, where the sum is over n-k and k is a generalized pentagonal number (A001318) <= n and the sign of the k-th term is (-1)^([(k+1)/2]). See A001318 for a good way to remember this!

其中，数列A001318是一种广义五边形数。

另外，符号位由确定广义五边形数的自变量的绝对值决定。

处理以上各种细节，最终可以得到\(p(n)\)的式子为：

\[ p(n)= \left \{\begin{aligned} &1 & & \text{if}\quad n=0 \\ &\sum_{|m|\ge1,\frac{m(3m-1)}{2}\leq n}(-1)^{m+1}p\left(n-\frac{m(3m-1)}{2}\right) & & \text{else} \end{aligned}\right. \]

由于广义五边形数增长是二次的，因此计算\(p(N)\)的时间复杂度缩减到了\(O(N\sqrt{N})\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from itertools import count

mod = 10 ** 6


def gen_pentagonal():
    for i in count(1, 1):
        yield i * (3 * i - 1) // 2
        yield i * (3 * i + 1) // 2


p = [1]

for n in count(1, 1):
    i = 0
    val = 0
    for m in gen_pentagonal():
        if m > n:
            break
        sgn = i >> 1 & 1
        if sgn == 0:
            val = (val + p[n - m]) % mod
        else:
            val = (val - p[n - m] + mod) % mod
        i += 1
    if val == 0:
        ans = n
        break
    p.append(val)
print(ans)