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} を満たす正整数列 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 を出力します．
