ABC150 D - Semi Common Multiple - あっとのTECH LOG

問題原文

atcoder.jp

問題要旨

長さ $N$ の偶数からなる正の整数列 $A$ と、正の整数 $M$ が与えられる。
$A$ の全ての要素 $a_k$ に対して、以下の条件を満たす正の整数 $X$ を $A$ の「半公倍数」と呼ぶことにする。

$X = a_k × (p + 0.5)$ を満たす負でない整数 $p$ が存在する。

$1$ 以上 $M$ 以下の整数のうち、 $A$ の半公倍数となるような数はいくつあるか？

$1 \leq N \leq 10^{5}$
$1 \leq N \leq 10^{9}$
$1 \leq a_i \leq 10^{9}$

解法

簡単な問題を考える

半公倍数は考えにくい。問題を簡単にして、求めたいものが公倍数の個数の場合、つまり $X$ の条件が以下の場合を考える。

$X = a_k × p$ を満たす負でない整数 $p$ が存在する。

この条件下では、 [a_k] は $X$ の約数でなければならないことがわかる。
逆に考えて、全ての $a_k$ に対して条件を満たすような $X$ は $a_1, a_2, ... a_k$ の LCMであることがわかる。

邪魔な0.5を消す

なんかLCMが使えそうなのがわかった。これを半公倍数の場合にしていきたいが、条件の $0.5$ が邪魔。なんとかして消したい。
そこで、条件式を一度展開してしまって、

$X = a_kp + \frac{a_k}{2}$ を得る。さらにこれを $\frac{1}{2}$ でくくると、
$X = \frac{a_k}{2}(2p + 1)$ が得られる。さらに、 $a_k$ は偶数なので、 $a_k' = \frac{a_k}{2}$ とすると、
$X = a_k'(2p + 1)$ が得られる。これで邪魔な $0.5$ が消えた！

問題文の再定義

ここまでで問題文は以下のようになった。

長さ $N$ の偶数からなる正の整数列 $A$ と、正の整数 $M$ が与えられる。
ここで、 $A$ の要素を全て $2$ で割ったものを $A'$ とする。
$A'$ の全ての要素 $a_k$ に対して、以下の条件を満たす正の整数 $X$ を $A$ の「半公倍数」と呼ぶことにする。
- $X = a_k' × (2p + 1)$ を満たす負でない整数 $p$ が存在する。
$1$ 以上 $M$ 以下の整数のうち、 $A$ の半公倍数となるような数はいくつあるか？
LCMが使えるかもしれないよ。

なんか少し簡単になった気がする。

実験をする

$N = 2$
$M = 10$
$A = [2, 4$ ]
を考えてみる。

まず $A$ の要素すべてを２で割って、 $A' = [1, 2$ ] を得る。
次に、 $X$ の式に当てはめて、
$X = 1 × (2p_1 + 1) = 2 × (2p_2 + 1)$ を満たすような、負でない整数 $p_1, p_2$ 、整数 $X$ が存在するかを考える。
少し考えると、そんなものは存在しないことがわかる。（ $1, 3, 5 ....$ , と、 $2, 6, 10 ....$ みたいになる。）
その理由を考えると、 $(2p + 1)$ の部分は、 $1, 3, 5, 7 ....$ と奇数しか取れないので、各 $a_k$ が持つ素因数としての２の数が同じでないとダメなことがわかる。（２以外の素数は必ず奇数で、奇数をいくらかけても奇数。奇数なら、 $(2p + 1)$ の部分でいかようにも）

LCMがとてつもなく大きくなることがある

答えが０になるパターンもわかったので、あとはLCMを使えばいい。でも、LCMがすごく大きくなるケースもある。でもよくよく考えると、 $M$ を超えるようなLCMの場合には意味がないことがわかる。

まとめ

$A$ の要素は全て２で割っておく（これを $A'$ とする）
$A'$ の各要素について、「２で割り切れる回数」が等しくないなら答えは0。
そうでないなら、各 $a_k'$ についてLCMを求めて、その奇数倍が答えになる。（ $(2p + 1)$ より）

実装

from math import ceil
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 2で割ったものに置き換え
A = [a // 2 for a in A]

# 各要素について、2で割り切れる回数が等しいかチェック
count_div_2 = None
for a in A:
    cnt = 0
    while a % 2 == 0:
        a //= 2
        cnt += 1

    if count_div_2 is None:
        count_div_2 = cnt
    elif cnt != count_div_2:
        print(0)
        exit()

# LCM計算
while len(A) > 1:
    a, b = A.pop(), A.pop()
    my_lcm = lcm(a, b)

    # Mを超えたlcmは意味がない
    if my_lcm > M:
        print(0)
        exit()

    A.append(my_lcm)


print(ceil(M // A[0] / 2))

感想

むずい！！！！！！！！！！！！wwwww