No.1097 Remainder Operation
タグ : / 解いたユーザー数 211
作問者 :
SSRS
/ テスター :
沙耶花
問題文
整数$X$があります。$X$の最初の値は$0$です。また、長さ$N$の数列$A_0,A_1,\cdots,A_{N-1}$が与えられます。
これから、以下の操作を繰り返し行います。
操作: $X$を$N$で割った余りを計算し、$r$とする。$X$に$A_r$を加える。
$Q$回のクエリが来ます。それぞれのクエリでは、正の整数$K$が与えられるので、$K$回目の操作の後の$X$の値を求めてください。
入力
$N$
$A_0 \ A_1 \ \cdots \ A_{N-1}$
$Q$
$K_1$
$K_2$
$\vdots$
$K_Q$
入力は以下の制約を満たします。
- 入力はすべて整数
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^6 (0 \leq i < N)$
- $1 \leq Q \leq 10^5$
- $1 \leq K_i \leq 10^{12} (1 \leq i \leq Q)$
出力
$Q$行出力してください。
$i (1 \leq i \leq Q)$行目には、$K_i$回目の操作の後の$X$の値を出力してください。
サンプル
サンプル1
入力
5 3 3 2 4 7 2 2 4
出力
7 16
$1$回目の操作では、$r=0$なので、$X=0+A_0=0+3=3$となります。
$2$回目の操作では、$r=3$なので、$X=3+A_3=3+4=7$となります。
$3$回目の操作では、$r=2$なので、$X=7+A_2=7+2=9$となります。
$4$回目の操作では、$r=4$なので、$X=9+A_4=9+7=16$となります。
よって、$2$回目と$4$回目の操作の後の$X$の値はそれぞれ$7, 16$なので、$7$と$16$を出力します。
サンプル2
入力
2 314159 141421 1 271828
出力
61919700120
オーバーフローに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。