問題一覧 > 通常問題

No.2075 GCD Subsequence

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
3 ProblemId : 8399 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-16 18:00:47

問題文

$\mathrm{gcd}(x,y)$ で $x$ と $y$ の最大公約数を表します。

長さ $N$ の整数列 $A$ が与えられます。$A$ の連続するとは限らない、長さ $1$ 以上の部分列 $A'=(A'_1,A'_2,\dots , A'_k)$ であって次の条件を満たすものの個数を求めてください。

  • $1 \le i \le k-1$ を満たす全ての整数 $i$ に対して $\mathrm{gcd}(A'_i,A'_{i+1})>1$

なお、答えは非常に大きくなる場合があるので答えを $998244353$ で割った余りを出力してください。

ただし、2 つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

  • $1 \le N \le 2×10^5$
  • $1 \le A_i \le 10^6 $
  • 入力は全て整数
  • 出力

    条件を満たす部分列の個数を $998244353$ で割った余りを出力してください。

    サンプル

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

    条件を持たすのは、$(1),(2),(3),(4),(2,4)$ の5つです。

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

    サンプル3
    入力
    10
    3 1 7 5 4 10 8 6 2 9
    出力
    58

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