No.983 Convolution

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 53
作問者 : tubuann1tubuann1 / テスター : beetbeet
6 ProblemId : 3874 / 出題時の順位表
問題文最終更新日: 2020-02-11 19:01:29

問題文

第 $0$ 項から第 $N-1$ 項までの $N$ 項からなる正の整数の列 $A$ があります。
ただし、$0$ 個以上のいくつかの項はその値を自由に決めることができます。
第 $0$ 項から第 $N-1$ 項までの $N$ 項からなる正の整数の列 $B$ を次のように定義します。

    $\displaystyle B_k = \sum_{i\& j=k} (A_i \times A_j)$
$\& $ は bitwise and を表します。
$B$ の全ての項の値を割り切るような最大の正の整数を $B$ の最大公約数と定義します。
$A$ の項の値を最適に決めたときの、$B$ の最大公約数の最大値を求めてください。
ただし、最大公約数の最大値が存在しない場合は、$-1$ を出力してください。

入力

$N$
$A_0\ A_1\ \ldots A_{N-1}$

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$ または $A_i=-1$
$A_i=-1$ のとき、かつそのときに限り第 $i$ 項の値を正の整数の範囲で自由に決めることができる
入力は全て整数である

出力

答えを一行に出力する。

サンプル

サンプル1
入力
3
-1 -1 -1
出力
-1

どれだけ大きな整数 $M$ に対しても、$M$ より最大公約数を大きくするような各項の決め方が存在する。

サンプル2
入力
5
7 9 3 5 1
出力
1

サンプル3
入力
5
-1 54 -1 12 -1
出力
36

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。