問題一覧 > 教育的問題

No.3357 Partial Sum of e mod Prime

レベル : / AI推定難易度 : 850 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 54
作問者 : 👑 p-adic / テスター : yu23578
お気に入りにしたユーザー ProblemId : 12528 / 自分の提出
問題文最終更新日: 2025-09-15 22:20:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 488 小数誤差コンテスト (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。