No.2176 LRM Question 1
MasKoaTS
箱星Problem Statement
You are given positive integers $L, R, M$. Find the remainder when the following value is divided by $M$.
$\displaystyle \sum_{n=L}^{R} \left( \prod_{i=1}^{n} \left( \prod_{j=1}^{i} j \right) \right)$
Definition of $\sum, \prod$ (click to expand)
For a sequence $a = ( a_{1}, a_{2}, \dots, a_{n} )$ of length $n$, $\displaystyle \sum_{i=l}^{r} a_{i}$ and $\displaystyle \prod_{i=l}^{r} a_{i}$ are defined as follows.
$\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}$
Here, $n,l,r$ are all integers satisfying $1 \leq l \leq r \leq n$.
Constraints
$1 \leq L \leq R \leq 10^{18}$
$1 \leq M \leq 10^{6}$
All input values are integers.
Input
The input is given in the following format.
$L$ $R$ $M$
The $1$st line contains $L, R, M$ in this order, separated by single-byte spaces.
Output
Output the answer on $1$ line.
Sample
Sample 1
Input
3 5 8
Output
4
Let $\displaystyle f(L,R) = \sum_{n=L}^{R} \left( \prod_{i=1}^{n} \left( \prod_{j=1}^{i} j \right) \right)$ and $\displaystyle i! = \prod_{j=1}^{i} j$. Then,
$f(3,5) = (1!)(2!)(3!) + (1!)(2!)(3!)(4!) + (1!)(2!)(3!)(4!)(5!)$, and
$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$
so $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$.
The remainder when this is divided by $8$ is $4$.
Sample 2
Input
2 2 2
Output
0
$f(2,2) = 2! = 2$, which is divisible by $2$.
Sample 3
Input
1 1000000000000000000 1000000
Output
6063
The value of $f(L,R)$ can be very large.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。