No.1809 Divide NCK
タグ : / 解いたユーザー数 122
作問者 :
MasKoaTS
/ テスター :
Kanten4205
ygussany
Problem Statement
You are given positive integers $N$, $K$, $M$.
Find the maximum non-negative integer $x$ such that the remainder when $_{N}C_{K}$ is divided by $M^{x}$ is $0$.
Here, the value of $_{N}C_{K}$ is defined as follows.
$\displaystyle _{N}C_{K} := \frac{N \times (N-1) \times \cdots \times (N-K+1)}{K \times (K-1) \times \cdots \times 1}$
Constraints
$1 \leq K \leq N \leq 10^{18}$
$2 \leq M \leq 10^{12}$
All inputs are integers
Input
The input is given in the following format.
$N$ $K$ $M$
The $1$st line contains $N$, $K$, and $M$ in this order, separated by single spaces
Output
Output the answer on $1$ line, followed by a newline.
Sample
Sample 1
Input
8 3 2
Output
3
$\displaystyle _{8}C_{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 = 7 \times 2^{3}$
Therefore, the maximum non-negative integer $x$ such that the remainder when $_{8}C_{3}$ is divided by $2^{x}$ is $0$ is $3$.
Sample 2
Input
1 1 1000000000000
Output
0
The answer is not necessarily a positive integer.
Sample 3
Input
12345678987654321 987654321 13579
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。