Almost All Divisors - #560 div3 d

#math #条件厳密

ans は, -1 でなければ, 数列の 2 数から作れる
sample
8
8 2 12 6 4 24 16 3
を sort する
2 3 4 6 8 12 16 24
ans = 48 = 2 * 24 = 3 * 16 = 4 * 12 = 6 * 8

各素因数ごとに最小何か求める
最小なのは, 他の素因数を加えると, 与えられた数列にない要素生み出してしまうから
上に挙げた sample なら,
ans = $2^4 * 3^1$

ans の候補
1. 互いに異なる素因数が 1 つの場合
肩を 1 増やしたもの
2
2 4
なら,
ans = $2^3$

2. それ以外
重複を込めた素因数の積
さっきの sample

ans が数列に入ってたら -1
ans がでかいと overflow で壊れるけど, そのとき数列の数にはないことはわかる
たまたま一致することある?
1
3 6

-1
ans = 6
2が入ってない

数列の数は 2 以上
ans は 1 にならない

ans の約数の個数 - 2 != N なら -1
数列の数は必ず, ans の約数に入ってる
2
2
2 4
1
4

8
-1

2 3 5 7 ...
っていう数列が来ることを考えると, ans の約数全列挙は時間計算量的に無理
このとき, ans は overflow で壊れてることに注意

3
1
999983
1
4
2
3 6

999966000289