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://webptt.com/cn.aspx?n=bbs/puzzle/M.1409496269.A.229.html ※ 编辑: tml (129.2.129.153), 08/31/2014 22:45:34