478. Mixtures
https://projecteuler.net/problem=478
有一混合物由三種物質A、B、C所構成。我們可用A、B、C的組成比例(a : b : c)來表示
此一混合物。例如，(2 : 3 : 5)就代表由20%的A、30%的B和50%的C混合而成的混合物。
在此一題目中，我們不能把這些物質單獨分離出來，但是可以藉由混合不同比例的混合物
來得到新的混合物。
舉例來說，我們可以混合(3 : 0 : 2)、(3 : 6 : 11)和(3 : 3 : 4)這三種混合物。
如果我們混合了10單位的第一種、20單位的第二種以及30單位的第三種混合物，
那我們就會得到新的混合物(6 : 5 : 9)，因為：
(10·3/5 + 20· 3/20 + 30·3/10 :
10·0/5 + 20· 6/20 + 30·3/10 :
10·2/5 + 20·11/20 + 30·4/10) = (18 : 15 : 27) = (6 : 5 : 9)
但是，由同樣那三種混合物卻配不出(3 : 2 : 1)這樣的混合物，因為這三種混合物中，
B的組成比例都比C少。
令n為一正整數，並假設對所有符合0≦a, b, c≦n以及gcd(a, b, c) = 1的整數數組
(a, b, c)，我們都擁有(a : b : c)此一混合物。令M(n)為所有這些混合物的集合。
例如，M(2)代表下列19種混合物的集合：
{(0 : 0 : 1), (0 : 1 : 0), (0 : 1 : 1), (0 : 1 : 2), (0 : 2 : 1),
(1 : 0 : 0), (1 : 0 : 1), (1 : 0 : 2), (1 : 1 : 0), (1 : 1 : 1),
(1 : 1 : 2), (1 : 2 : 0), (1 : 2 : 1), (1 : 2 : 2), (2 : 0 : 1),
(2 : 1 : 0), (2 : 1 : 1), (2 : 1 : 2), (2 : 2 : 1)}。
令E(n)代表M(n)裡有多少子集能用來組出混合物(1 : 1 : 1)，即含有等量A、B、C的
混合物。
可以驗證E(1) = 103、E(2) = 520447、E(10) mod 11^8 = 82608406以及
E(500) mod 11^8 = 13801403。
請求出E(10000000) mod 11^8。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.2.129.153
※ 文章網址: http://www.ptt.cc/bbs/puzzle/M.1409496269.A.229.html
※ 編輯: tml (129.2.129.153), 08/31/2014 22:45:34