Semi Common Multiple [AtCoder Beginner Contest 150 D]

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

解説

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

式中に小数が出てくるのは面倒なので、小数が出てこないような形にしよう。
A[k]は偶数なので、A[k] = 2 * B[k]とおくと、
X = A[k] * (p + 0.5)
X = B[k] * (2p + 1)
これを見てみると、B[k]の奇数倍の数が作られることになる。
それはいいけど、そこからどうする？

競技プログラミングでアルゴリズムを考えるときに、似てる問題に対するアルゴリズムをもじるという方針がある。
今回でいうと、公倍数を数えるとしたときに、どうやって解くかを考えてみよう。
公倍数は最小公倍数の倍数となるという性質がある。
これだと、全部の数の最小公倍数を取って、M÷最小公倍数をすると答えが得られる。

最小公倍数を計算するには、最大公約数を求めることで求めることができ、
最大公約数はユークリッドの互除法を用いるのが良い。
やり方はネットで解説され尽くされているので、ググって欲しい。

今回の問題も多分これ。
B[k]の最小公倍数を取って、Mで割ればいいが、これだと奇数倍も偶数倍も含まれてしまう。
なので、更に2で割って、切り上げたものが答え。
この辺は入力例を見てエスパーした。

が・・・ダメッ！
冷静にWA数を見てみると、10個くらいWAしている。
経験上、このくらいのWAだったら、コーナーケースっぽいのを踏んでいる感じがする。

実験するが、奇数倍での公倍数を数えていくので、これは愚直解が簡単にかけそう。
これを書く。
書いて実験すると、
2 20
2 4
でダメなことが分かる。
あ、そうか、1,2で公倍数取ると、2になって、2=1*2だから奇数倍にならんのか。
最小公倍数を取ったときに、各B[i]の奇数倍になってることを確認する。
なってないなら、0を答える。

int N, M, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
int naive() {
    int ans = 0;
    
    rep(x, 1, M + 1) {
        bool ok = true;
        rep(i, 0, N) {
            if (x % B[i] != 0) ok = false;
            if ((x / B[i]) % 2 == 0) ok = false;
        }
        if (ok) {
            printf(">> %d\n", x);
            ans++;
        }
    }

    return ans;
}
//---------------------------------------------------------------------------------------------------
int solve() {
    ll lc = 1;
    rep(i, 0, N) lc = lcm(lc, B[i]);

    rep(i, 0, N) if ((lc / B[i]) % 2 == 0) return 0;

    ll ans = M / lc;
    ans = (ans + 1) / 2;
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) B[i] = A[i] / 2;

    //cout << naive() << endl;
    cout << solve() << endl;
}