問題一覧 > 通常問題

No.1097 Remainder Operation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 211
作問者 : SSRS / テスター : 沙耶花
9 ProblemId : 4385 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-06-25 22:19:36

問題文

整数Xがあります。Xの最初の値は0です。また、長さNの数列A0,A1,⋯,AN−1が与えられます。
これから、以下の操作を繰り返し行います。

操作: XをNで割った余りを計算し、rとする。XにArを加える。

Q回のクエリが来ます。それぞれのクエリでは、正の整数Kが与えられるので、K回目の操作の後のXの値を求めてください。

入力

N
A0 A1 ⋯ AN−1
Q
K1
K2
⋮
KQ

入力は以下の制約を満たします。

  • 入力はすべて整数
  • 1≤N≤105
  • 1≤Ai≤106(0≤i<N)
  • 1≤Q≤105
  • 1≤Ki≤1012(1≤i≤Q)

出力

Q行出力してください。
i(1≤i≤Q)行目には、Ki回目の操作の後のXの値を出力してください。

サンプル

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

1回目の操作では、r=0なので、X=0+A0=0+3=3となります。
2回目の操作では、r=3なので、X=3+A3=3+4=7となります。
3回目の操作では、r=2なので、X=7+A2=7+2=9となります。
4回目の操作では、r=4なので、X=9+A4=9+7=16となります。
よって、2回目と4回目の操作の後のXの値はそれぞれ7,16なので、7と16を出力します。

サンプル2
入力
2
314159 141421
1
271828
出力
61919700120

オーバーフローに注意してください。

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