AOJ - Farey Sequence
Farey Sequence | Aizu Online Judge
問題名から察せるとおり, n群目のファレイ数列の要素数を数える問題です. $n-1$群目のファレイ数列までわかっていると仮定したとき, $n$番目のファレイ数列の要素数は($n-1$群目の要素数+nと互いに素なn未満の自然数の数)となります.
dp[i] := i番目のファレイ数列の要素数
dp[0] := 1
dp[1] := 2
とすると, 更新式は
dp[i+1] = dp[i] + phi[i+1]
とかけます. phi[i] はi未満の自然数であってiと互いに素な自然数の個数を表します. phi[i]を事前に求めておく必要がありますが, これはオイラーのΦ関数を用いて求めることができます. しかし, オイラーのΦ関数を用いるためにはそれぞれの数を素因数分解する必要があり, 愚直にNまでの自然数を素因数分解してからΦ関数を計算すると, O(N^(3/2))となり, 間に合いません. そこで, エラストテネスの篩とのアナロジーを用いて, 次のような手続きを考えます.
1. phi[i] = i として求めたいN番目の要素まで初期化しておく
2. i = 2 ~ Nまで以下を回す
phi[i] == i のとき,iの倍数の添字を持つもの(自身を含む)を(i-1)/i倍する. その他のときなにもしない.
この操作を行うことで, 配列phiにΦ関数を実現できます. 素数を発見してその素因数を持ちうるものに対して先んじて(i-1)/iをかけることを繰り返すと, 最終的にすべての要素がΦ関数と同じ計算をすることになります.
これを求めた後でdpを更新してクエリに答えればOKです. アルゴリズムはエラストテネスのふるいと同じものを使っているので, O(N log log n)になると思います(多分).
