問題
2つの数列AとBが与えられる。引数に数列をとるLCMという関数を定義する。LCMは与えられた数列の全ての組み合わせにおける最大公倍数の集合を返す。LCM(A)==LCM(B)となるかを確認せよ。
解法
LCMの返り値を計算するととなる。数列内で余分な要素を削除することで、等しい結果になるかは確認できる。余分な要素とは、すでにある要素で構成できる要素のことである。
例として{2,3,4,6}を考える。6は{2,3}で作ることができるので6は余分な要素となる。
計算量
GCD:
繰り返し回数:
全体: