No.752 mod数列
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 :
%20
/ テスター :
nmnmnmnmnmnmnm
タグ : / 解いたユーザー数 56
作問者 :
%20
/ テスター :
nmnmnmnmnmnmnm
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。