시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB63392963.043%

문제

The $(i,j)$th binomial coefficient, denoted $C(i,j)$, is the (zero-indexed) $j$th entry of the (zero-indexed) $i$th row in Pascal's triangle:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

where $C(0,0) = 1$ and the $(i+1)$st row can be computed from the $i$th row using the recursion $$C(i+1, j) = C(i,j) + C(i, j-1),$$ treating as $0$ any out-of-bounds entries of the triangle on the right-hand side.

Given $N$ and $K$, compute how many entries in the first $N+1$ rows of Pascal's triangle are multiples of $K$. To be precise: for how many pairs of indices $(i,j)$ with $0\leq i\leq N$ and $0 \leq j \leq i$, is $C(i,j)$ divisible by $K$?

입력

The single line of input contains two positive integers $N$ $(1 \leq N \leq 10^3)$ and $K$ $(1 \leq K \leq N)$, with meaning as described above.

출력

Print the number of entries in the first $N+1$ rows of Pascal's triangle that are divisible by $K$.

예제 입력 1

5 3

예제 출력 1

3

예제 입력 2

1000 4

예제 출력 2

394315

출처

ICPC > Regionals > North America > Mid-Central Regional > 2024 Mid-Central USA Programming Contest J번

  • 문제를 만든 사람: Christian Yongwhan Lim