けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 150 D - Semi Common Multiple (400 点)

面白かった!!!
「2 で何回割れるのか」に着目するのはあるあるだけど、400 点としては難しめな感じかな。

問題へのリンク

問題概要

 N 個の正の整数  a_{0}, \dots, a_{N-1} と整数  M が与えられる。以下の条件を満たす整数  x が何個あるか求めよ。

  •  1 \le x \le M
  • 任意の  i (= 0, 1, \dots, N-1) に対して、ある 0 以上の整数  p が存在して、 x = a_{i} \times (p + 0.5) が成立する

制約

  •  1 \le N \le 10^{5}
  •  1 \le M \le 10^{9}
  •  a_{i} は 2 以上の偶数

考えたこと

まず  a_{i} は偶数なので、全部 2 で割っておくと、実質的に問題は

  •  a_{0}, 3a_{0}, 5a_{0}, \dots
  •  a_{1}, 3a_{1}, 5a_{1}, \dots
  •  \dots
  •  a_{N-1}, 3a_{N-1}, 5a_{N-1}, \dots

のすべての系列に含まれるような整数  x ( M 以下) の個数を求める問題ということになる。ここで、いきなり考えると大変なので、2 つの系列について考えてみることにする。

2 系列問題

  •  a, 3a, 5a, \dots
  •  b, 3b, 5b, \dots

の両方に含まれるということは

  •  pa = qb

を満たす奇数  p, q が存在するということ。ここで、 p, q は奇数なので、

  •  a b の「2 で割れる回数」は等しくなければならない

ということがわかる。なぜなら  pa qb とをそれぞれ素因数分解したときに、双方の 2 の指数が等しくなければならない。が、 p にも  q にも 2 が含まれないので、結局  a における 2 の指数と、 b における 2 の指数が等しくなければならない。

逆に、 a b の 2 の指数が等しいならば、

  •  a = 2^{K}A ( A は奇数)
  •  b = 2^{K}B ( B は奇数)

としたときに、 pa = qb は、 pA = qB となる。つまり、元の問題において「 a b も奇数の場合」に帰着されたわけだ。こうなると実は簡単で、

  •  A B の公倍数は、 A B の最小公倍数を  L として、 L の倍数である
  • ただし、 2L とか  4L とかはダメ。 pA = qB = 4L とかだと  p, q が偶数になってしまう
  •  pA = qB = L, 3L, 5L, \dots が条件を満たす

まとめると、


  •  a, b を 2 で割れる回数が等しいことが必要なので、あらかじめ 2 で割れるだけ割ってしまう ( M もついでにその回数分だけ  M =  M / 2 (小数点切り捨て) とする)。そして、

  •  L = {\rm LCM}(a, b) として、 L, 3L, 5L, \dots が答え

一般の場合

ここまで 2 個の場合を考えたけど、 N 個の場合も同様。

  •  a_{0}, a_{1}, \dots, a_{N-1} を「2 で割れる回数」が等しいことが必要なので、あらかじめ 2 で割れるだけ割っておく ( M も)
  •  L = {\rm LCM}(a_{0}, a_{1}, \dots, a_{N-1}) として、 L, 3L, 5L, \dots が答え
#include <iostream>
#include <vector>
using namespace std;

long long GCD(long long x, long long y) {
    if ( y == 0) return x;
    else return GCD(y, x % y);
}

long long solve(int N, long long M, vector<long long> &a) {
    // 2 で割れるだけ割る (割れる回数が異なったらダメ)
    bool same = true;
    while (a[0] % 2 == 0) {
        for (int i = 0; i < N; ++i) {
            if (a[i] % 2 != 0) return 0;
            a[i] /= 2;
        }
        M /= 2;
    }
    for (int i = 0; i < N; ++i) if (a[i] % 2 == 0) return 0;

    // lcm
    long long lcm = 1;
    for (int i = 0; i < N; ++i) {
        long long g = GCD(lcm, a[i]);
        lcm = lcm / g * a[i];
        if (lcm > M) return 0;
    }
    return (M / lcm + 1) / 2;
}

int main() {
    int N; long long M;
    cin >> N >> M;
    vector<long long> a(N);

    // あらかじめ a は一回 2 で割っておく
    for (int i = 0; i < N; ++i) cin >> a[i], a[i] /= 2;
    cout << solve(N, M, a) << endl;
}