No.752 mod数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 33
作問者 : %20%20 / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
3 ProblemId : 2158 / 出題時の順位表

問題文

$a_n=P\bmod n\ (n=1,2,\dots)$ とします。
与えられた各 $L_i,R_i\ (i=1,2,\dots,Q)$ に対して、$\displaystyle\sum_{n=L_i}^{R_i}a_n$ の値を答えてください。

入力

$P$ $Q$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

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

  • $1\le P\le10^9$
  • $1\le Q\le10^5$
  • $1\le L_i\le R_i\le 10^9$
  • 入力はすべて整数である

出力

$\sum_{n=L_1}^{R_1}a_n$
$\sum_{n=L_2}^{R_2}a_n$
$\vdots$
$\sum_{n=L_Q}^{R_Q}a_n$

$i$ 行目が $\sum_{n=L_i}^{R_i}a_n$ の値になるように、$Q$ 行出力してください。

サンプル

サンプル1
入力
23 1
1 7
出力
16

$\sum_{n=1}^7a_n=0+1+2+3+3+5+2=16$ です。

サンプル2
入力
3000 4
7 36
1 2491
2934 3000
1542 5231
出力
263
1465544
2211
7756611

$P\lt R_i$ となる場合があります。

サンプル3
入力
319586423 10
88 861
4641915 12591875
40 93620
4 58503
41376643 99181970
8388 351105
4029987 4171876
184091372 270441885
45972 65554518
8313 52186
出力
180038
34469822716416
2189413228
855085983
2015105445915363
30802594433
294723880788
7971861707449373
1053080394476134
663106681

答えが $2^{32}$ よりも大きくなる場合があります。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。