問題一覧 > 通常問題

No.917 Make One With GCD

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 181
作問者 : ningenMeningenMe / テスター : finefine
13 ProblemId : 3305 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-10-25 07:49:55

問題文

$N$個の要素からなる数列$A$が与えられます。$i$番目($1 \le i \le N$)の要素は$A_i$です。この数列の空ではない部分列を考えます。
ここで部分列とは「数列の要素を$0$個以上いくつか選んで削除し、残ったものを元の順序を保って並べた数列」を表します。
含まれる全ての要素の最大公約数が$1$となるような数列$A$の部分列の総数を求めてください。

ある2つの部分列に関して、その要素の値が全て一致しても元の数列における要素が異なるものが含まれている場合、その部分列は異なるものとして扱うことに注意してください。

入力

$N$
$A_{1}\ A_{2}\ \dots\ A_{N}$

入力は全て整数である
$1 \le N \le 50$
$1 \le A_i \le 10^8 (1 \le i \le N)$

出力

最後に改行してください。

サンプル

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

{1},{1,2},{1,3},{2,3},{1,2,3}の5つの部分列は最大公約数が1となります。

サンプル2
入力
4
1 1 1 1
出力
15

要素の値が全て一致しても元の数列における要素が異なるものが含まれている場合、その部分列は異なるものとして扱うことに注意してください。

サンプル3
入力
4
2 4 8 16
出力
0

どのように部分列を選んでも、最大公約数が1になるものはありません。

サンプル4
入力
10
801754 703742 332182 68016 914814 8470 937255 293192 313080 501971
出力
763

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