[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 \) があるということです。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; // 最大公約数 ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); } // 最小公倍数 ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } int main() { int N; ll M; cin >> N >> M; ll a[N]; ll b = 0; for (int i = 0; i < N; i++) { cin >> a[i]; b = max(b, a[i] / 2); } ll l = 1; for (int i = 0; i < N; i++) { l = lcm(l, a[i] / 2); if (l > M) { cout << "0\n"; return 0; } } for (int i = 0; i < N; i++) { ll t = l / (a[i] / 2); if (t % 2 == 0) { cout << "0\n"; return 0; } } cout << (M - l) / (2 * l) + 1<< "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません