問題一覧 > 通常問題

No.1262 グラフを作ろう!

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 32
作問者 : PCTprobabilityPCTprobability / テスター : nok0nok0
3 ProblemId : 5021 / 出題時の順位表
問題文最終更新日: 2020-10-16 22:30:10

問題文

正整数 $N,M$ と長さが $M$ の正数列 $A$ が与えられます。

以下の方法で関数 $f(a, b)$ を定義します。

頂点に$0,1,...,N-1$ の番号がついた $N$ 頂点を用意し、変数 $X:=a-1, Y:=(X-b)mod\ a$ とします。 そして以下の操作を行います。

  • 頂点 $X$ から 頂点 $Y$ へ有向辺を張る。
  • $X=Y$, $Y=(Y-b)mod\ a$ とする。
  • もし頂点 $a-1$ を始点, 終点とする閉路が存在すれば、 $f(a,b) = $ 閉路に含まれる最小の頂点番号 と定め、操作を終了する。
  • またこの時閉路は単純閉路とし、そのような閉路は $1$ 通りに定まることが保証されます。(21:52追記)
  • そうでなければ操作を最初から繰り返す。

このとき $\sum_{i = 0}^{M-1}\sum_{j = 1}^{A_i}f(A_i,j)$ を求めてください。

入力

$N$ $M$
$A_0$ $A_1$ ...$A_{M-1}$

・入力は全て整数である。
・$1 \le N,M \le 10^6$
・$1 \le A_i \le N$

出力

$\sum_{i = 0}^{M-1}\sum_{j = 1}^{A_i}f(A_i,j)$ を求めてください。最後に改行してください。

サンプル

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

$f(3,1)+f(3,2)+f(3,3)$ を求めます。 $f(3,1)$ を考えます。

  • 始め $x=2,y=1$ です。ここで頂点 $2$ と頂点 $1$ を結びます。まだ頂点 $2$ を始点、終点とする閉路はないので操作を続けます。
  • $x=1,y=0$ となっています。頂点 $1$ と頂点 $0$ を結びます。まだ頂点 $2$ を始点、終点とする閉路はないので操作を続けます。
  • $x=0,y=2$ となっています。頂点 $0$ と頂点 $2$ を結びます。ここで頂点 $2$ を始点、終点とする閉路が生まれ、その閉路に含まれる最小の頂点番号は $0$ なので $f(3,1)=0$ となります。

サンプル2
入力
100 5
23 34 54 99 57
出力
746

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