問題一覧 > 通常問題

No.752 mod数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : %20%20 / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
5 ProblemId : 2158 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-03-09 03:44:31

問題文

$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}$ よりも大きくなる場合があります。

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