화성인 친구

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N과 k가 주어질 때, N!을 k진법으로 표기했을 때 끝에 붙는 0의 개수를 구합니다.

난이도: 보통10점 중 4점
유형: 수학, 정수론
정답자: 아직 제출이 없습니다

문제

10학년 학생 바샤는 화성인 흐룰과 친구다. 오늘 흐룰이 바샤에게 $N!$ 의 끝에 0이 몇 개 붙는지 구하는 문제를 풀어 달라고 부탁했다. 바샤는 처음에 기뻤다. 5학년 때 수학 올림피아드 동아리에서 이런 문제를 푼 적이 있었기 때문이다. 그러다 화성에서는 $k$ 진법을 쓴다는 사실이 떠올라 생각에 잠겼다.

바샤가 $N!$ 을 $k$ 진법으로 표기했을 때 끝에 붙는 0의 개수를 세는 것을 도와주자.

입력

두 정수 $N$ 과 $k$ 가 주어진다. ( $1 \le N \le 10^{18}$ , $2 \le k \le 10^{9}$ )

출력

정수 하나를 출력한다. 그 값은 $N!$ 을 $k$ 진법으로 표기했을 때 끝에 붙는 0의 개수이다.

예제1

예제 1
입력
```
20 7
```
예상 출력
```
2
```