問題一覧 > 通常問題

No.3187 Mingle

レベル : / AI推定難易度 : 2125 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 39
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 12359 / 自分の提出
問題文最終更新日: 2025-06-20 22:31:07
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 471 (順位表) の他の問題:

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$.
In this case, the number of operations is $2$, and the probability of this outcome is $\frac{1}{15}$.

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