ABC150 D. Semi Common Multiple - phyllo’s algorithm note

問題

長さNの偶数の整数からなる正数列Aと整数Mが与えられる。
任意のk(1<=k<=N)に対して、以下の条件を満たす正の整数XをAの半公倍数と定義する。

X = A_k * (p + 0.5)を満たす負でない整数pが存在する

1以上M以下の整数のうち、Aの半公倍数の個数を求めよ。

制約

1 <= N <= 10^5
1 <= M <= 10^9
2 <= A_i <= 10^9
A_iは偶数

解法

Xについて考える。
0.5を1/2として整理すると、
X = (A_k/2) * (2*p+1)
と書ける。
ここで右辺を見ると、(A_k/2)は任意の自然数、(2*p+1)は1以上の奇数になっている。

Xとしてあり得るものを考えると、
Xが奇数の場合、(A_k/2)もすべて奇数である必要があり、そうならば(A_k/2)の最小公倍数の奇数倍はすべて満たせる。
Xが偶数の場合、(2*p+1)が奇数なので、(A_k/2)もすべて偶数である必要がある。しかも、偶数であるだけでなく、Xを素因数分解してでてくる2^xのxと(A_k/2)を素因数分解してでてくる2^yのyは同じである必要がある。すべての(A_k/2)の素因数分解してでてくる2^xのxが等しいならば、Xは普通に(A_k/2)の最小公倍数の奇数倍はすべて満たせる。そうでなければXは存在しない。

M以下の(A_k/2)の最小公倍数の奇数倍の個数は、(A_k/2)の最小公倍数をLとすると、(M/L+1)/2で求められる。
また、最小公倍数はかなり大きくなり得るが、M以上になった時点で答えは0になるので、そこで打ち切って桁あふれしないようにする。