3964번: 팩토리얼과 거듭제곱

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	1277	205	155	19.042%

문제

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

팩토리얼 진영의 유명한 장군 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를 한 줄에 하나씩 출력한다.

예제 입력 1

2
5 2
10 10

예제 출력 1

3
2

W3sicHJvYmxlbV9pZCI6IjM5NjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMjlcdWQxYTBcdWI5YWNcdWM1YmNcdWFjZmMgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMyMThcdWQ1NTkgXHViMDk4XHViNzdjXHVjNWQwIFx1YzgwNFx1YzdjMVx1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwYWNcdWIyZTQuIFx1ZDMyOVx1ZDFhMFx1YjlhY1x1YzViYyBcdWM5YzRcdWM2MDFcdWFjZmMgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxIFx1YzljNFx1YzYwMVx1Yzc0MCBcdWIyMDRcdWFjMDAgXHVjMjE4XHVkNTU5IFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWM5YzBcdWJjMzBcdWQ1NjAgXHVhYzgzXHVjNzc4XHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMmY4XHVjNmIwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMzI5XHVkMWEwXHViOWFjXHVjNWJjIFx1YzljNFx1YzYwMVx1Yzc1OCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjN2E1XHVhZDcwIG5cdWM3NDAgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWQzMjlcdWQxYTBcdWI5YWNcdWM1YmMgXHVhY2M0XHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YmE3NFx1YzExYyBcdWQ2YzhcdWI4MjhcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxXHVjOWM0XHVjNjAxXHVjNzU4IFx1YzgxY1x1YjNjNSBrXHViMjk0IFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM1ZDAgaVx1YzgxY1x1YWNmMVx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IGlcdWI5N2MgXHViOWNjXHViNGU0XHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNGRjXHViNTE0XHVjNWI0IFx1YzYyNFx1YjI5OFx1Yzc0MCBuXHVhY2ZjIGtcdWFjMDAgXHVjMmY4XHVjNmIwXHViMjk0IFx1YjBhMFx1Yzc3NFx1YjJlNC4ga1x1YjI5NCBuXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNFx1YzExYyBcdWM3OTFcdWM3NDAgXHVjMjE4XHViODVjIFx1YjljY1x1YjRlNFx1YzViNCBcdWJjODRcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmE4NyBcdWIxNDRcdWIzZDlcdWM1NDggXHVkNmM4XHViODI4XHVjNzQ0IFx1YzljNFx1ZDU4OVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NFx1YzgxYyBrXHViMjk0IG5cdWM3NDQgXHViMDk4XHViMjA0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNmM4XHViODI4XHVjNzQ0IFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWJhYThcdWI0NTAgXHVjMTMxXHVjN2E1XHVkNTg4XHVjNzNjXHViYmMwXHViODVjLCBuIVx1YzY0MCBrPHN1cD5pPFwvc3VwPlx1YzY0MCBcdWMyZjhcdWM2YjBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzRcdWI1NGMsIG4hXHVjNzQ0IGs8c3VwPmk8XC9zdXA+XHViODVjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgaVx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgVCAmbGU7IDEwMCkgXHViMmU0XHVjNzRjIFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjZmMga1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgMTA8c3VwPjE4PFwvc3VwPiwgMiAmbGU7ICZuYnNwO2sgJmxlOyAxMDxzdXA+MTI8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAwXHVjN2E1IFx1ZDA3MCBpXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzOTY0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmFjdWx0eSBEaXZpZGluZyBQb3dlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkZyZWQgRmFjdWx0eSBhbmQgUGF1bCBQb3dlciBsb3ZlIGJpZyBudW1iZXJzLiBEYXkgYWZ0ZXIgZGF5IEZyZWQgY2hvb3NlcyBhIHJhbmRvbSBpbnRlZ2VyIG4gYW5kIGhlIGNvbXB1dGVzIG4hLiBIaXMgZnJpZW5kIFBhdWwgYW11c2VzIGhpbXNlbGYgYnkgY29tcHV0aW5nIHNldmVyYWwgcG93ZXJzIG9mIGhpcyByYW5kb21seSBjaG9zZW4gaW50ZWdlciBrIGxpa2UgazxzdXA+MjxcL3N1cD4sIGs8c3VwPjM8XC9zdXA+LCAuLi4gYW5kIHNvIG9uLiBPbiBhIGhvdCBzdW1tZXIgZGF5LCBGcmVkIGFuZCBQYXVsIGdvdCByZWFsbHksIHJlYWxseSBib3JlZCwgc28gdGhleSBkZWNpZGVkIHRvIHBsYXkgYSBqb2tlIG9uIHRoZWlyIGJ1ZGR5IERhdmUgRGl2aWRlci4gRnJlZCBjaG9vc2VzIGEgcmFuZG9tIGludGVnZXIgbiB3aGlsZSBQYXVsIGNob29zZXMgYSByYW5kb20gaW50ZWdlciBrLiBUaGV5IHdhbnQgRGF2ZSB0byBmaW5kIHRoZSBiaWdnZXN0IGludGVnZXIgaSBzdWNoIHRoYXQga2kgZGl2aWRlcyBuISB3aXRob3V0IGEgcmVtYWluZGVyLCBvdGhlcndpc2UgdGhleSB3aWxsIHRocm93IGEgY2FrZSBpbiBEYXZlJiMzOTtzIGZhY2UuIEJlY2F1c2UgRGF2ZSBkb2VzIG5vdCBsaWtlIGNha2VzIGluIGhpcyBmYWNlLCBoZSB3YW50cyB5b3UgdG8gaGVscCBoaW0gZmluZGluZyB0aGF0IGludGVnZXIgaS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0Jm5ic3A7KDEgJmxlOyBUICZsZTsgMTAwKS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIHQgbGluZXMgY29udGFpbnMgdGhlIHR3byBudW1iZXJzIG4sJm5ic3A7ayAoMiAmbGU7IG4gJmxlOyAxMDxzdXA+MTg8XC9zdXA+LCAyICZsZTsgJm5ic3A7ayAmbGU7IDEwPHN1cD4xMjxcL3N1cD4pIHNlcGFyYXRlZCBieSBvbmUgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCB0aGUgbWF4aW11bSBpbnRlZ2VyIGkgb24gYSBzZXBhcmF0ZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2011 A번

문제를 번역한 사람: baekjoon

문제

문제

출처

ICPC

3964번 - 팩토리얼과 거듭제곱 다국어

문제

입력

출력

제한

예제 입력 1

예제 출력 1

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

3964번 - 팩토리얼과 거듭제곱 다국어

문제

입력

출력

제한

예제 입력 1 복사

예제 출력 1 복사

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

예제 입력 1

예제 출력 1