きままにものづくり

日々の気付いたことなんかを書いてます。

SRM611Div1Easy

問題

2つの数列AとBが与えられる。引数に数列をとるLCMという関数を定義する。LCMは与えられた数列の全ての組み合わせにおける最大公倍数の集合を返す。LCM(A)==LCM(B)となるかを確認せよ。

解法

LCMの返り値を計算すると O(2^N)となる。数列内で余分な要素を削除することで、等しい結果になるかは確認できる。余分な要素とは、すでにある要素で構成できる要素のことである。
例として{2,3,4,6}を考える。6は{2,3}で作ることができるので6は余分な要素となる。

計算量

GCD: O(log N)
繰り返し回数: O(N^2)
全体:  O(N^2 log N)

コード