시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 513 182 131 38.757%

문제

음이 아닌 정수 N와 소수(prime number) A가 주어지면, N!을 Ak로 나누었을 때, 나머지가 0이 되는 최대의 음이 아닌 정수 k를 구하여라. (단, N!=N×(N-1)×···×1, 0!=1)

입력

첫째 줄에 정수 N과 A가 사이에 공백을 두고 주어진다. (0 ≤ N < 231, 2 ≤ A ≤ 11, A는 소수)

출력

첫째 줄에 최대의 음이 아닌 정수 k를 출력한다.

예제 입력 1

5 2

예제 출력 1

3

5!=5×4×3×2×1=120이고, 120은 23으로 나눈 나머지가 0이다. 조건을 만족하며 3보다 큰 k의 값은 존재하지 않으므로 k의 최댓값은 3이다.

출처