No.3187 Mingle
Problem Statement
You are given a positive integer $N$ that is at least $3$ and a prime $P$. You also have a variable $a$, initialized to $a = N$.
You repeatedly perform the following operation until $a$ becomes $2$ or less.
- Choose a non-negative integer $b$ between $1$ and $a$, inclusive, uniformly at random. Let $c$ be the remainder when $a$ is divided by $b$, and replace $a$ with $a - c$. Here, $b$ is chosen independently for each operation.
Find the expected number of operations modulo $\mathrm{mod} \ P$.
Here, only inputs $N, P$ for which the answer is defined modulo $\mathrm{mod} \ P$ are given.
Strictly speaking, it is guaranteed that for the given $N$, the expected number of operations is always a rational number and can be expressed as $\frac{x}{y}$ using coprime non-negative integers $x, y$. It is also guaranteed that $y \not\equiv 0 \ (\mathrm{mod} \ P)$ for the given $P$. Then a non-negative integer $z$ satisfying $yz \equiv x \ (\mathrm{mod} \ P), 0 \leq z < P$ is uniquely determined, so output this $z$.
Input
$N\ \ P$
- $3 \leq N \leq 3 \times 10^5$
- $9 \times 10^8 \leq P \leq 10^9$
- $P$ is prime
- All input values are integers
- The answer is defined modulo $\mathrm{mod} \ P$
Output
Output the expected number of operations modulo $\mathrm{mod} \ P$, followed by a newline.
Sample
Sample 1
Input
5 998244353
Output
332748125
For example, the following sequence of operations is possible.
- In the $1$st operation, choose $b = 3$. Since $c = 2$, $a$ is replaced with $5 - 2 = 3$.
- In the $2$nd operation, choose $b = 2$. Since $c = 1$, $a$ is replaced with $3 - 2 = 1$.
It can be proved that the expected number of operations is $\frac{22}{3}$.
Sample 2
Input
50 998244353
Output
411546056
Sample 3
Input
500 998244353
Output
854038998
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
蜜蜂