みんなのプロコン2018 決勝 A - Uncommon
問題概要
自然数N,M と 数列 {a_i} (0 <= i < N) が与えられる.
各 j = 1, ... ,M について, jと互いに素なa_iの要素の数を求めよ.
1 <= N,M,a_i <= 105
解法
各jについて, 互いに素でない <-> 共通因数を持つ a_i の数を考えることにしよう.
j = 5 のように j が素数であれば,その倍数を数えるだけで良い. これは倍数全列挙をすれば高速に求めることができる.
(関連問題)として, 各 j について a_i のうちで j の倍数となっているもの,すなわち j を約数として持っているものを求めることにする.
倍数全列挙は, Xまでの j = 1,.., Yの倍数を全列挙していくアルゴリズムで
各jに対してXまでの倍数の数は X/j で抑えられるから, O(X * (1/1 + 1/2 + .. + 1/Y) ) = O(XlogY) だけかかる.
* 類題 ARC068 E
X = max(a_i, M), Y = M とすればよく, この場合だと O(max(a_i,M) logM) 程度になる.
これを使って , factor[ k ] := (k を倍数として持つ数の集合) = (k の約数の集合) を埋めることができて
例えば factor[ 12 ] = { 1, 2, 3, 4, 6, 12 } となる.
各 j について, cnt[ j ] := ( a_i のうち, j を約数として持つものの要素数 ) と定義して,
各 a_i について, 各 factor[ a_i ] の要素 x について cnt[x] をインクリメントしていけば cnt[ j ]を求めることができ, (関連問題) が解けた.
factor[ a_i ] の要素が最大でいくつあるかということだが,公式解説と同様の考察をすると,
9! = 3 * 105 から, 最大でも8個になる(公式だとfactorを素数に限定しているのでより小さい)
よって(関連問題)は O(NlogM + 8*N) で十分. (正しい書き方ではないが簡便のため)
元の問題について考える.
上のアルゴリズムを少し変えて,倍数全列挙で各 j が素数の時のみfactorに自身の倍数を足していく,とすれば
各 k に対して prime_factor[ k ] := ( k を倍数として持つ素数の集合) = ( k の素因数の集合) が求められそうだ.
素数の時, というのはエラトステネスの篩のように考えると, prime_factor が空である時なのでこれは簡単にわかる.
つまり, prime_factor[ 12 ] = { 1, 2, 3 }
かつ, prime_factor の数も同様に6個以下になる.
ここで {a_i} のうちで j と互いに素でないものはprime_factor[ j ] と 関連問題で求めた cnt[x] を使えば,包除原理で求めることができる.
例えば12であれば (2または3の倍数) = cnt[2] + cnt[3] - cnt[6] となる.
包除原理の実装は, lambdaを使って再帰的に実装しても良さそうだが,
単純に s := (prime_factor のうちどれを選ぶかの mask )
として, s の立っているbitの数で+か-を選んで足していくのが楽そう.
prime_factor の要素数は6以下なので, 26程度の定数倍にしかならない.
ここまでをまとめると,
factor=> cnt => prime_factor => 包除原理で j と互いに素でないものを求める
となるが, このfactorは余計で prime_factorだけ求めておき,
prime_factor のうちのいくつかを組み合わせてかけた数についてのみ, cnt[ j ]テーブルを埋めれば十分である.
これは (2かつ3の倍数の数) = cnt[ 6 ] は必要であって, cnt[ 12 ] は包除原理で必要ないからである.
よって prime_factor => cnt => 包除原理 として, この問題が解けた.
メモ
難しかった. でも包除原理の実装やら良問.
