← 返回题目列表

AtCoder · past23_g

G. 长总和

中文机器翻译题面 查看原题

问题陈述

给你一个序列 A 长度 N.
序列 B 是无限次重复 A.
更准确地说,定义 B_i = A_{((i-1)\ {\rm mod}\ N) + 1} 对于所有整数 i,其中 p\ {\rm mod}\ q 表示当 p 除以 q.

回答以下问题 Q 查询。 i第一个查询是:

  • 求总和 L_i-th 通过 R_i第项 B.

约束

  • 所有输入值均为整数。
  • 1 \le N \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 0 \le A_i \le 10^6
  • 1 \le L_i \le R_i \le 10^{12}

输入

输入由标准输入按以下格式给出:

N Q
A_1 A_2 \dots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

输出

打印 Q 行。
的 i- 第行应包含以下问题的答案 i-第一个查询。


示例输入 1

8 5
3 1 4 1 5 9 2 6
3 7
6 10
1 16
4 21
1 1000000000000

示例输出 1

21
21
62
68
3875000000000

我们有 B=(3,1,4,1,5,9,2,6,3,1,4,1,5,9,2,6,\dots).

此输入包含五个查询。前两个如下。

  • 对于 1-st查询,求总和 3-rd 通过 7第项: 4+1+5+9+2 = 21.
  • 对于 2-nd查询,求总和 6-th 通过 10第项: 9+2+6+3+1=21.