[AtCoder] ABC 150 D – Semi Common Multiple

問題

方針

式の変形

整数を考えるうえで、\( X = a_k (p + 0.5) \) という式の \( 0.5 \) という部分は考えにくいので、式の変形を行います。\( a_k \) は偶数なので自然数 \( b_k,\) を用いて、 \( a_k = 2b_k \) とします。また、問題を考える都合で、整数 \( p_k \) を用いて、\( X \) は

\[X = b_k(2p_k + 1)\]

と表現できます。この問題は、\( M \) 以下の \( X \) について、\( X \) を固定した時、上記を満たす \( p_k \) が存在することを確かめれば良いです。

最小公倍数

上記の式変形により、\( X \) は\( b_k \) の倍数である必要があります。ここで、\( l \) を \( b_k \ (1 \leq k \leq N) \) の最小公倍数とします。よって、\( X \) の候補は、自然数 \( m \) を用いて、

\[ X = l m\]

と表せます。また、\( l \leq M \) を満たす必要があります。ここで、\( p_k \) が存在することを確かめます。

\[\begin{eqnarray}
lm &=& b_k(2p_k + 1)\\
2p_k &=& \dfrac{lm}{b_k} – 1
\end{eqnarray}\]

ここで、\( l \) は \( b_k \) の倍数であることに注意して、次の場合分けを考えます。また、\( n \) を自然数とします。

\( \dfrac{l}{b_k}\) が偶数のとき

このとき、

\[\dfrac{lm}{b_k} = 2n\]

と表現できるので、\( p_k \) に関する方程式は、

\[2p_k = 2n – 1\]

となります。この式を満たす \( p_k \) は存在しません。

\( \dfrac{l}{b_k}\) が奇数のとき

このとき、

\[\dfrac{lm}{b_k} = (2n – 1)m\]

と表現できるので、\( p_k \) に関する方程式は、

\[ 2p_k = (2n – 1)m – 1\]

となります。よって、\(m \) が奇数ならば、\( p_k \) が存在することが分かります。したがって、\( 1\leq k \leq N \) について、この条件を満たすとき、整数 \( t \) を用いて、\( m = 2t + 1\) とし、

\[ l(2t+1) \leq M\]

を満たす最大の \( t \) は、

\[ t = \left \lfloor\dfrac{M – l}{2l} \right \rfloor \]

となるので、答えは、\( t + 1 \) となります。これは、

\[ t = 0, 1, \cdots ,  \left \lfloor\dfrac{M – l}{2l} \right \rfloor \]

を満たす \( t \) について \( X \) があるということです。

コード