README.md

[Gold II] 팩토리얼과 거듭제곱 - 3964

문제 링크

성능 요약

메모리: 22108 KB, 시간: 1272 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2024년 1월 8일 10:40:35

문제 설명

수학 나라에 전쟁이 일어났다. 팩토리얼 진영과 거듭제곱 진영은 누가 수학 나라를 지배할 것인지 결정하기 위해 싸우고 있다.

팩토리얼 진영의 유명한 장군 n은 자기 자신을 팩토리얼 계산을 하면서 훈련을 하고 있고, 거듭제곱진영의 제독 k는 자기 자신에 i제곱을 하기 위해 i를 만들고 있었다.

드디어 오늘은 n과 k가 싸우는 날이다. k는 n을 나누어서 작은 수로 만들어 버리기 위해서 몇 년동안 훈련을 진행하고 있었다.

이제 k는 n을 나누려고 한다. 훈련을 통해서 모두 성장했으므로, n!와 kⁱ와 싸우는 것이다.

이때, n!을 kⁱ로 나눌 수 있는 가장 큰 i를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 100) 다음 T개의 줄에는 n과 k가 공백으로 구분되어 주어진다. (2 ≤ n ≤ 10¹⁸, 2 ≤ k ≤ 10¹²)

출력

각각의 테스트 케이스에 대해서, 가장 큰 i를 한 줄에 하나씩 출력한다.