No.3357 Partial Sum of e mod Prime
Note
The execution time limit for this problem is 10000[ms].
The execution time limit is very strict, so we recommend using a fast language and implementation.
For reference, the execution times of the writer's implementations of the intended solution are 1661[ms] in C, 1717[ms] in C++, 1683[ms] in cLay, 733[ms] in PyPy3, and 10000[ms] or more (that is, TLE) in Python3.
Problem Statement
You are given a prime number $P$.
$\displaystyle \left( \sum_{i=0}^{P-1} \frac{1}{i!} \right) \bmod P $
Find this value.
Click here to expand the definition of the value $q \bmod P$ modulo $P$ of a rational number $q$ whose irreducible fraction representation has a denominator that is not a multiple of $P$
Let $\frac{n}{d}$ ($d > 0$) be the irreducible fraction representation of $q$.
Since $P$ is prime and $d$ is not a multiple of $P$, there uniquely exists an integer $x$ satisfying $0 \leq x < P$ and $dx \equiv n \pmod{P}$.
We denote this as $q \bmod P$, the value of $q$ modulo $P$.
Background
This section explains the background for readers familiar with number theory. Given a sequence of rational numbers $(q_i)_{i=0}^{\infty}$, whether its series
$\displaystyle \sum_{i=0}^{\infty} q_i $
converges to a real number and, if it does, what properties its limit has (whether it is rational or irrational, algebraic or transcendental, and so on) are difficult questions in general.
Now, for any prime $p$, assume that there exists a non-negative integer $i$ such that $q_i$ has no fractional representation whose denominator is not a multiple of $p$, and let $n_p$ be the minimum such value. If $n_p \to \infty$ as $p \to \infty$, consider the partial sum modulo $p$
$\displaystyle \left( \sum_{i=0}^{n_p-1} q_i \right) \bmod p $
for each $p$; the asymptotic behavior of the resulting sequence is expected to retain some information about the original series. For example, the values describing the asymptotic behavior of the sequences obtained by applying this construction to the series giving multiple zeta values are the finite multiple zeta values, which are conjectured to be deeply related to multiple zeta values and are still being studied in number theory.
This problem is nothing other than computing an intermediate value of the sequence obtained by applying the above construction to the series representation of $e$.
Input
The input is given from standard input in $1$ line in the following format:
- The $1$st line contains $P$.
$P$
Constraints
The input satisfies the following constraints:
- $P$ is a prime number satisfying $1 \leq P \leq 10^8$.
Output
Output the answer in $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
2
Output
0
$\displaystyle \sum_{i=0}^{P-1} \frac{1}{i!} = \frac{1}{0!} + \frac{1}{1!} = 1 + 1 = 2 $
and $2 \bmod P = 2 \bmod 2 = 0$.
Sample 2
Input
3
Output
1
$\displaystyle \sum_{i=0}^{P-1} \frac{1}{i!} = \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} = 1 + 1 + \frac{1}{2} = \frac{5}{2} $
and
$\displaystyle \frac{5}{2} \bmod P = \frac{5}{2} \bmod 3 = 1 $
holds.
Sample 3
Input
5
Output
0
$\displaystyle \sum_{i=0}^{P-1} \frac{1}{i!} = \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} = 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} = \frac{65}{24} $
and
$\displaystyle \frac{65}{24} \bmod P = \frac{65}{24} \bmod 5 = 0 $
holds.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。