374. Maximum Integer Partition Product
http://projecteuler.net/problem=374
所謂一個整數 n 的分割就是將 n 寫成一些正整數的和。
如果兩種分割只差在排列不同的話就視為同一種分割。
所謂「相異分割」則是分割的各個正整數至多出現一次。
5 的所有相異分割一共有 5, 4+1, 3+2 三種。
令 f(n) 表示 n 的所有相異分割各數的乘積中最大的那個，
m(n) 表示出現上述乘積的分割有幾個數。
由此可知 f(5) = 6 及 m(5) = 2。
對 n=10 最大乘積出現在 10 = 2+3+5，於是知 f(10) = 30 及 m(10) = 3，
兩者的乘積 f(10) * m(10) = 30 * 3 = 90。
給定 Σf(n)*m(n), 1≦n≦100 的答案是 1683550844462。
求 Σf(n)*m(n), 1≦n≦10^14。
請回答此數除以 982451653 的餘數 (這是第五千萬個質數)。
--
竟然出整數分割...orz
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
All Comments