No.917 Make One With GCD

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 99
作問者 : ningenMeningenMe / テスター : finefine
2 ProblemId : 3305 / 出題時の順位表

問題文

$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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。