No.2176 LRM Question 1
タグ : / 解いたユーザー数 143
作問者 :
MasKoaTS
/ テスター :
箱星
👑 
potato167
問題文
正整数 $L, R, M$ が与えられます。次の値を $M$ で割った余りを求めてください。
$\displaystyle \sum_{n=L}^{R} \left( \prod_{i=1}^{n} \left( \prod_{j=1}^{i} j \right) \right)$
$\sum, \prod$ の定義（クリックで展開）
長さ $n$ の数列 $a = ( a_{1}, a_{2}, \dots, a_{n} )$ に対して、$\displaystyle \sum_{i=l}^{r} a_{i}$ 及び $\displaystyle \prod_{i=l}^{r} a_{i}$ は次のように定義されます。
$\displaystyle \sum_{i=l}^{r} a_{i} = a_{l} + a_{l+1} + \cdots + a_{r}$
$\displaystyle \prod_{i=l}^{r} a_{i} = a_{l} \times a_{l+1} \times \cdots \times a_{r}$
ただし、$n,l,r$ はいずれも $1 \leq l \leq r \leq n$ を満たす整数とします。
制約
$1 \leq L \leq R \leq 10^{18}$
$1 \leq M \leq 10^{6}$
入力はすべて整数
入力
入力は次の形式で与えられます。
$L$ $R$ $M$
$1$ 行目には $L, R, M$ がこの順に半角スペース区切りで与えられる
出力
答えを $1$ 行に出力してください。
サンプル
サンプル1
入力
3 5 8
出力
4
$\displaystyle f(L,R) = \sum_{n=L}^{R} \left( \prod_{i=1}^{n} \left( \prod_{j=1}^{i} j \right) \right)$, $\displaystyle i! = \prod_{j=1}^{i} j$ とすると、
$f(3,5) = (1!)(2!)(3!) + (1!)(2!)(3!)(4!) + (1!)(2!)(3!)(4!)(5!)$ であり、
$1! = 1$
$2! = 1 \times 2 = 2$
$3! = 1 \times 2 \times 3 = 6$
$4! = 1 \times 2 \times 3 \times 4 = 24$
$5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$
なので、$f(3,5) = 1 \times 2 \times 6 + 1 \times 2 \times 6 \times 24
+ 1 \times 2 \times 6 \times 24 \times 120 = 34860$ です。
これを $8$ で割った余りは $4$ となります。
サンプル2
入力
2 2 2
出力
0
$f(2,2) = 2! = 2$ であり、これは $2$ で割り切れます。
サンプル3
入力
1 1000000000000000000 1000000
出力
6063
$f(L,R)$ の値は非常に大きくなる可能性があります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。