http://projecteuler.net/index.php?section=problems&id=73
PDFをさらに読み進めると、こんな解法が。
f(n)を値が与えられた範囲の分母がn以下の分数の個数、g(n)をそのうち既約の分数の個数とします。0から1の範囲でn = 12のとき、分母と分子の最大公約数が3の分数を考えます。これは、
3/12 3/9 3/6 6/9 9/12
これらは分母分子を3で割ることで既約分数になります。
1/4 1/3 1/2 2/3 3/4
すなわち、g(4)に対応しているわけです。この3を1〜12まで変えて足しあわせると、
f(12) = g([12/1]) + g([12/2]) + … + g([12/12])
となります。f(n)は大学入試レベルで簡単に求まるので、メビウスの反転公式を使います。
g(n) = μ(1)f([n/1]) + μ(2)f([n/2]) + … + μ(n)f([n/n])
μ(n)はメビウス関数です。メビウス関数はエラトステネスのふるい的に簡単に求められます。これで、従来より5倍速くなりました。
これは、まさにProblem 319と同じ形です。しかし、Problem 319は1010までメビウス関数を求めなければならないため、この解法では非常に時間がかかります。
