Semi Common Multiple - abc 150 d

#math #lcm #偶奇

解法

とりあえず, 小数点が嫌
2X = $a_k$ * (2p + 1)
左辺偶数, 2p + 1 = (奇数) より, $a_k$ 偶数
$a_k$ に奇数があったら 0 を出力して終わり

$a_k$ : 偶数より,
$a_k$ * (p + 0.5) = $\frac{a_k}{2} * (2p + 1)$

例 1

とりあえず sample1 で実験
2 50
6 10

6 10 を 3 5 にする
p + 0.5 を 2p + 1 にしていい

X = 3 * (2 $p_1$ + 1) = 5 * (2 $p_2$ + 1)
答えを見ると, 15, 45

確かに, 3 と 5 の最小公倍数 15 の倍数を作れる
15 : (2 $p_1$ + 1) = 5, (2 $p_2$ + 1) = 3
30 : (2 $p_1$ + 1) = 10, (2 $p_2$ + 1) = 6
45 : (2 $p_1$ + 1) = 15, (2 $p_2$ + 1) = 9

ここで, 2 $p_k$ + 1 は奇数
30 は作れない

例 2

少し拡張した例を考えたい
3 50
6 10 ?
の ? を何にするか

15 の約数 (1, 15 を除く) は 3, 5 のみ
45 の約数に 9 がある
? = 9 * 2 = 18 としてみよう

3 50
6 10 18

6 10 18 を 3 5 9 とする
p + 0.5 を 2p + 1 にしていい

X = 3 * (2 $p_1$ + 1) = 5 * (2 $p_2$ + 1) = 9 * (2 $p_3$ + 1)
3, 5, 9 の最小公倍数 45 の倍数を作れる

例 3

答えが 0 になる sample 2
3 100
14 22 40

14, 22, 40 を 7, 11, 20 とする

X = 7 * (2 $p_1$ + 1) = 11 * (2 $p_2$ + 1) = 20 * (2 $p_3$ + 1)

7, 11, 20 の最小公倍数は偶数
X が偶数
(2 $p_1$ + 1) : 奇数より, 7 * (2 $p_1$ + 1) : 奇数
よって 0

よって, $a_1, a_2, ..., a_k$ をその最大公約数でわっても 2 の倍数が残ってたら 0
このとき, M もその最大公約数で割ることに注意

$a_1, a_2, ..., a_k$ は, 上記の変更を終えたものとする
まず 2 でわり, $a_1, a_2, ..., a_k$ の最大公約数で割る
M も $a_1, a_2, ..., a_k$ の最大公約数で割る

L = ( $a_1, a_2, ..., a_k$ の最小公倍数)

答えは, M 以下の, L の倍数のうち, 奇数のもの
例 1 でいうと, 15, 30, 45 のうち, 15, 45
M = 44 だったら, 15 のみ

cnt = M / L

これは, cnt / 2 + (cnt % 2)