三浦と窮理とブログ

自分の経験したことを検索可能にしていくブログ.誰かの役に立ってくれれば嬉しいです.

ABC150D - Semi Common Multipleまとめ

Atcoder ABC150D D - Semi Common Multiple

時間内にはできませんでした.解説を見ながらやり直したのでまとめます.

a = { a₁ ,a₂ ,... ,aN }

a/2 = { a₁/2 ,a₂/2 ,... ,aN/2 }

と表すことにします.a が偶数列なので,a/2 は整数列です.a の半公倍数と a/2の公倍数に着目して考えていきます.

考えたこと

X が半公倍数である条件は次のように書き換えられます.

X が a の半公倍数であるとは, \begin{align} X = \frac{a _ 1}{2} (2p _ 1 + 1) = \frac{a _ 2}{2} (2p _ 2 + 1) = \cdots = \frac{a _ N}{2} (2p _ N + 1) \end{align} を満たす 0 以上の整数列 p₁ ,p₂ ,... ,pN が存在することである.

この条件より,a の半公倍数の集合は a/2 の公倍数の集合に含まれていることが分かります.ちなみに任意の公倍数は最小公倍数の倍数ですので, a の半公倍数が存在する場合,それは a/2 の最小公倍数の倍数です.

この条件を頭に入れて, a/2 の最小公倍数を求めてみます.これを L とします.

すなわち L は \begin{align} L = \frac{a _ 1}{2} q _ 1 = \frac{a _ 2}{2} q _ 2 = \cdots = \frac{a _ N}{2} q _ N \end{align} を満たす0以上の整数列 q₁ ,q₂ ,... ,qN が存在する最小の数です.

次に L が a の半公倍数であるかを確認します.

もし,q₁ ,q₂ ,... ,qN が全て奇数であれば条件(1)を満たすので L は a の半公倍数です.そして集合の包含性から,L は a の最小半公倍数であることも言えます.そして,a の任意の半公倍数は L の奇数倍です.L の奇数倍の個数を 1以上M以下の範囲で数えて出力します.

そうではなく,q₁ ,q₂ ,... ,qN の中に偶数が1つ以上存在すれば L は a の半公倍数ではありません.そして L を何倍しても a の半公倍数になることはありません.0 を出力します.

ACコード

Submission #9412600 - AtCoder Beginner Contest 150