問題一覧 > 通常問題

No.1809 Divide NCK

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 117
作問者 : MasKoaTSMasKoaTS / テスター : Kanten4205Kanten4205 ygussanyygussany
4 ProblemId : 7032 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-28 18:36:20

問題文

正整数 $N$, $K$, $M$ が与えられます。

$_{N}C_{K}$ を $M^{x}$ で割った余りが $0$ となるような非負整数 $x$ の最大値を求めてください。

ただし、$_{N}C_{K}$ の値は次のように定義されます。

  $\displaystyle _{N}C_{K} := \frac{N \times (N-1) \times \cdots \times (N-K+1)}{K \times (K-1) \times \cdots \times 1}$

制約

  • $1 \leq K \leq N \leq 10^{18}$

  • $2 \leq M \leq 10^{12}$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $K$ $M$

  • $1$ 行目には $N$ と $K$ と $M$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

サンプル1
入力
8 3 2
出力
3

$\displaystyle _{8}C_{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 = 7 \times 2^{3}$

なので、$_{8}C_{3}$ を $2^{x}$ で割った余りが $0$ となるような非負整数 $x$ の最大値は $3$ です。

サンプル2
入力
1 1 1000000000000
出力
0

答えが正整数になるとは限りません。

サンプル3
入力
12345678987654321 987654321 13579
出力
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。