[AtCoder] ABC 150 D – Semi Common Multiple

2020年1月12日2020年12月15日

問題

方針

式の変形

整数を考えるうえで、\( 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;
}