Problem 478

Mixtures

Let us consider mixtures of three substances: A, B and C. A mixture can be described by a ratio of the amounts of A, B, and C in it, i.e., (a : b : c). For example, a mixture described by the ratio (2 : 3 : 5) contains 20% A, 30% B and 50% C.

For the purposes of this problem, we cannot separate the individual components from a mixture. However, we can combine different amounts of different mixtures to form mixtures with new ratios.

For example, say we have three mixtures with ratios (3 : 0 : 2), (3 : 6 : 11) and (3 : 3 : 4). By mixing 10 units of the first, 20 units of the second and 30 units of the third, we get a new mixture with ratio (6 : 5 : 9), since:

(10·³/₅ + 20·³/₂₀ + 30·³/₁₀ : 10·⁰/₅ + 20·⁶/₂₀ + 30·³/₁₀ : 10·²/₅ + 20·¹¹/₂₀ + 30·⁴/₁₀) = (18 : 15 : 27) = (6 : 5 : 9)

However, with the same three mixtures, it is impossible to form the ratio (3 : 2 : 1), since the amount of B is always less than the amount of C.

Let n be a positive integer. Suppose that for every triple of integers (a, b, c) with 0 ≤ a, b, c ≤ n and gcd(a, b, c) = 1, we have a mixture with ratio (a : b : c). Let M(n) be the set of all such mixtures.

For example, M(2) contains the 19 mixtures with the following ratios:

{(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)}.

Let E(n) be the number of subsets of M(n) which can produce the mixture with ratio (1 : 1 : 1), i.e., the mixture with equal parts A, B and C.
We can verify that E(1) = 103, E(2) = 520447, E(10) mod 11⁸ = 82608406 and E(500) mod 11⁸ = 13801403.
Find E(10 000 000) mod 11⁸.

混合物

考虑由三种成份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·³/₅ + 20·³/₂₀ + 30·³/₁₀ : 10·⁰/₅ + 20·⁶/₂₀ + 30·³/₁₀ : 10·²/₅ + 20·¹¹/₂₀ + 30·⁴/₁₀) = (18 : 15 : 27) = (6 : 5 : 9)

然而，用同样的三种混合物，永远无法配置出比例为(3 : 2 : 1)的混合物，因为成分B的量永远比成分C要少。

记n是一个正整数。假设对于任意整数a，b，c满足0 ≤ a, b, c ≤ n且gcd(a, b, c) = 1，我们都有一种比例是(a, b, c)的混合物。记M(n)是所有这些混合物的集合。

例如，M(2)包含有下列19种不同比例的混合物：

记E(n)是能够构成混合物比例(1 : 1 : 1)的M(n)的子集数目。
可以验证E(1) = 103，E(2) = 520447，E(10) mod 11⁸ = 82608406，E(500) mod 11⁸ = 13801403。
求E(10 000 000) mod 11⁸。