*[[Problem 478:http://projecteuler.net/problem=478]] 「混合物」 [#e3929d35]
3つの材料 ''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) の比率を持つ3つの混合物があるとしよう. 1番目の混合物を10ユニット, 2番目の混合物を20ユニット, 3番目の混合物を30ユニット使って混ぜ合わせると, (6 : 5 : 9) の比率を持つ混合物が得られる.~
(10·&sup{3};/&sub{5}; + 20·&sup{3};/&sub{20}; + 30·&sup{3};/&sub{10}; : 10·&sup{0};/&sub{5}; + 20·&sup{6};/&sub{20}; + 30·&sup{3};/&sub{10}; : 10·&sup{2};/&sub{5}; + 20·&sup{11};/&sub{20}; + 30·&sup{4};/&sub{10};) = (18 : 15 : 27) = (6 : 5 : 9)
一方, この3つの混合物を使って (3 : 2 : 1) の比率にすることはできない, というのも ''B'' の量が常に ''C'' の量よりも少なくなるからだ.
正の整数 '''n''' を定義しよう. 3つの整数 ('''a''', '''b''', '''c''') に対し 0 ≤ '''a''', '''b''', '''c''' ≤ '''n''', gcd('''a''', '''b''', '''c''') = 1 となるような ('''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)}.
比率 (1 : 1 : 1), すなわち ''A'', ''B'', ''C'' が等しく含まれる混合物を作成できる M('''n''') の部分集合の個数を E('''n''') としよう.~
E(1) = 103, E(2) = 520447, E(10) mod 11&sup{8}; = 82608406, そして E(500) mod 11&sup{8}; = 13801403 が与えられている.~
E(10 000 000) mod 11&sup{8}; を求めよ.
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
