No.983 Convolution
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 :
tubuann1
/ テスター :
beet
タグ : / 解いたユーザー数 71
作問者 :
tubuann1
/ テスター :
beet
問題文最終更新日: 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)$
$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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。