No.3357 eの部分和 mod 素数
タグ : / 解いたユーザー数 44
作問者 : 👑
p-adic
/ テスター :
yu23578
注意
この問題の実行時間制限は10000[ms]です。
実行時間制限が非常に厳しいので、高速な言語・処理系の使用をおすすめいたします。
参考までに、想定解のwriter実装の実行時間はC言語で1661[ms]、c++で1717[ms]、cLayで1683[ms]、PyPy3で733[ms]、Python3で10000[ms]以上（すなわち TLE）です。
問題文
素数 $P$ が与えられます。
$\displaystyle \left( \sum_{i=0}^{P-1} \frac{1}{i!} \right) \bmod P $
を求めてください。
分母が $P$ の倍数でない既約分数表示を持つ有理数 $q$ の法 $P$ での値 $q \bmod P$ の定義はこちら（クリックで開く）
$q$ の既約分数表示を $\frac{n}{d}$（$d > 0$）と置きます。
$P$ が素数であり $d$ が $P$ の倍数でないという仮定から、$0 \leq x < P$ かつ $dx \equiv n \pmod{P}$ を満たす整数 $x$ が一意に存在します。
これを $q$ の法 $P$ での値 $q \bmod P$ と書き表します。
背景
整数論を知っている人向けの背景を説明します。有理数列 $(q_i)_{i=0}^{\infty}$ が与えられている時、その級数
$\displaystyle \sum_{i=0}^{\infty} q_i $
が実数に収束するか否かや、収束した場合にどのような性質を持つか（有理数か無理数か、代数的数か超越数か、など）は一般には難しい問題です。
ここで任意の素数 $p$ に対し、分母が $p$ の倍数でない分数表示を $q_i$ が持たないような非負整数 $i$ が存在すると仮定してその最小値を $n_p$ と置きます。もし $p \to \infty$ とした時に $n_p \to \infty$ となるのであれば、法 $p$ 部分和
$\displaystyle \left( \sum_{i=0}^{n_p-1} q_i \right) \bmod p $
を $p$ ごとに考えて得られる列の漸近挙動が元の級数の情報をある程度持っていることが期待されます。例えば多重ゼータ値を与える級数に対してこの構成をして得られる列の漸近挙動を記述する値が有限多重ゼータ値であり、多重ゼータ値との深い関係が予想されており現在も整数論で研究されています。
本問は $e$ の級数表示に対して上述の構成をして得られる列の途中の値を計算する問題にほかなりません。
入力
入力は以下の形式で標準入力から $1$ 行で与えられます：
- $1$ 行目に $P$ が与えられます。
$P$
制約
入力は以下の制約を満たします：
- $P$ は $1 \leq P \leq 10^8$ を満たす素数である。
出力
答えを $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2
出力
0
$\displaystyle \sum_{i=0}^{P-1} \frac{1}{i!} = \frac{1}{0!} + \frac{1}{1!} = 1 + 1 = 2 $
であり、$2 \bmod P = 2 \bmod 2 = 0$ です。
サンプル2
入力
3
出力
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} $
であり、
$\displaystyle \frac{5}{2} \bmod P = \frac{5}{2} \bmod 3 = 1 $
です。
サンプル3
入力
5
出力
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} $
であり、
$\displaystyle \frac{65}{24} \bmod P = \frac{65}{24} \bmod 5 = 0 $
です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。