No.1809 Divide NCK
タグ : / 解いたユーザー数 113
作問者 :
MasKoaTS
/ テスター :
Kanten4205
👑 
ygussany
追記（2022/04/25）
yukicoderの数式表示がMathJaxからKaTeXへ移行したことに伴い、問題文・解説の更新を行いました。
何か不備等ありましたら、作問者の方までご一報いただけると幸いです。
問題文
正整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。