\[S_k = \sum_{n=1}^k a_n\]

とする. このとき,

\[\sum_{n=L_i}^{R_i} a_n = S_{R_i} - S_{L_i-1}\]

となる.

さて, \(L_i, R_i\) は大きい可能性があるので, 愚直に計算するのはもちろん間に合わないし, 累積和を計算しておく方法も前処理で間に合わないしメモリも足りない.

そこで, \(\lfloor P/n \rfloor = m\) となる \(n\) について考える. このとき, 余りは \(P - nm\) となるので, \(n\) が増えると \(m\) ずつ減る等差数列となる. \(\lfloor P/n \rfloor = m\) となる最大の \(n\) までの和を \(m\) が大きい方から順に計算 (等差数列の和は公式が使える) して, 累積和を取っておく. こうすることで \(S_k\) を求めるには \(\lfloor P/k \rfloor\) を求め, 累積和と等差数列の和の公式を使えばいいことになる.

ただし, この方法だと \(m\) は最大で \(P\) となるのでやはり間に合わないしメモリも足りない. そこで, \(m = 10^4\) となる \(n\) より大きい \(n\) についてはこの方法を使い, それ未満の \(n\) については愚直に余りを計算して累積和を取っておくようにするという, ハイブリッド方式を使えばいい.