No.1036 Make One With GCD 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 111
作問者 : ningenMeningenMe / テスター : chocoruskchocorusk
16 ProblemId : 4072 / 出題時の順位表
問題文最終更新日: 2020-04-26 02:19:26

問題文

$N$個の要素からなる数列$A$が与えられます。$i$番目($1 \le i \le N$)の要素は$A_i$です。この数列の空ではない連続する部分列を考えます。
含まれる全ての要素の最大公約数が$1$となるような数列$A$の連続する部分列の総数を求めてください。

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

補足

writer解は、python3ではTLEでした。pypy3ではACを確認しています。
【2020/04/26追記】コンテスト時よりいくつかテストケースを追加し、解説を修正しています。

入力

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

入力は全て整数である
$1 \le N \le 500000$
$1 \le A_i \le 10^{18} (1 \le i \le N)$

出力

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

サンプル

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

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

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

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

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

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

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

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