AtCoder ABC150 D - Semi Common Multiple

コンテスト本番だと解けそうにない…。

問題

https://atcoder.jp/contests/abc150/tasks/abc150_d

考察

条件式を変形すると「任意の\(k\)に対して\(\frac{X}{a_k} - \frac{1}{2}\)が非負整数か」と言い換えられ、\(a_k = 2b_k\)とおくと更に「任意の\(k\)に対して\(\frac{1}{2} (\frac{X}{b_k} - 1)\)が非負整数か」と言い換えることができる。よって、任意の\(k\)に対して\(\frac{X}{b_k}\)が奇数であれば条件を満たす。

この条件を満たすためにまず、\(X\)がすべての\(b_k\)で割り切れる必要がある。つまり\(X\)は、すべての\(b_k\)の最小公倍数（\(L\)とおく）の倍数でなければならない。

次に、すべての\(\frac{L}{b_k}\)は奇数でなければならない。もし偶数のものがひとつあれば、それは\(L\)を何倍しても偶数のままなので条件を満たすことはない。更に、\(L\)の倍数は\(1\)以上の奇数である必要があることもわかる。

よって、次の条件式を満たす\(1\)以上の奇数\(c\)の個数を数えればいい。

$$cL \le M\ (c = 1, 3, ...)$$

\(c = 2c' - 1\)とおくと、次のような式になる。

$$(2c' - 1)L \le M\ (c' = 1, 2, ...)$$

これを変形して次の式を得る。

$$c' \le \frac{M + L}{2L}$$

\(c'\)の個数は、この条件式を満たす\(c'\)の最大値と等しい。よって、次が答えである。

$$\lfloor \frac{M + L}{2L} \rfloor$$

実装

https://atcoder.jp/contests/abc150/submissions/9870019

void solve() {
  int n, m;
  cin >> n >> m;
  vi32 a(n);
  cin >> a;
  rep(i, n) a[i] /= 2;
  i64 l = 0;
  rep(i, n) {
    l = lcm(l, a[i]);
    if (l > m) {
      cout << 0 << endl;
      return;
    }
  }
  rep(i, n) {
    if ((l / a[i]) % 2 == 0) {
      cout << 0 << endl;
      return;
    }
  }
  cout << (m + l) / (2 * l) << endl;
}

感想

最小公倍数がオーバーフローしないよう注意して実装する必要がある。…と思ったけど、そのチェックがなくてもACした。