問題一覧 > 通常問題

No.1809 Divide NCK

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

問題文

正整数 NN, KK, MM が与えられます。

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

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

  NCK:=N×(N−1)×⋯×(N−K+1)K×(K−1)×⋯×1\displaystyle _{N}C_{K} := \frac{N \times (N-1) \times \cdots \times (N-K+1)}{K \times (K-1) \times \cdots \times 1}

制約

  • 1≤K≤N≤10181 \leq K \leq N \leq 10^{18}

  • 2≤M≤10122 \leq M \leq 10^{12}

  • 入力はすべて整数

入力

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

NN KK MM

  • 11 行目には NN と KK と MM がこの順に半角スペース区切りで与えられる

出力

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

サンプル

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

8C3=8×7×63×2×1=56=7×23\displaystyle _{8}C_{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 = 7 \times 2^{3}

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

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

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

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

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