엔트 수

시간 제한1초메모리 제한128 MB

요약

한 번 진행할 때마다 값을 1 줄인 뒤 자릿수는 그대로 두고 밑을 1 올리는Goodstein과 비슷한 수열을 따라가며, 항이 0이 되는 밑을 구하거나 2^60 전에 0에 도달하지 않음을 판정한다.

난이도: 보통10점 중 7점
유형: 구현, 수학, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

엔트(Ent)는 가운데땅(Middle-earth)에 사는 나무를 닮은 종족으로, 숲을 지키는 오래된 목자들입니다. 빌보가 엔트들을 만나려고 팡고른 숲을 찾았을 때, 그들의 기록에서 아주아주 긴 수들을 발견하고 가장 나이 많은 엔트인 나무수염에게 그 의미를 묻습니다. 나무수염은 이 수들이 어떤 수열들의 수렴 속도를 나타낸다고 설명합니다(이 수열은 로이벤 굿스타인(Reuben Goodstein)이라는 수학자가 엔트들에게 소개한 것입니다). 며칠에 걸친 설명 끝에 빌보는 마침내 이런 수들이 어떻게 만들어지는지 이해하게 됩니다.

두 수 $N$ 과 $B$ 로 정의되는 수열을 생각합시다. 수열의 첫 항은 밑 $B$ 로 나타낸 $N$ 자신입니다. 다음 항을 얻으려면 현재 수를 1 줄인 뒤, 그 결과의 각 자릿수는 그대로 둔 채 밑 $B$ 를 1 늘립니다.

예를 들어 $N = 42$ , $B = 10$ 에서 시작해 봅시다. 각 자리를 괄호로 묶어 (4)(2) Base 10처럼 씁니다. 다음 항은 (4)(1) Base 11이며, 이는 10진법으로 45입니다. 먼저 1을 빼서 (4)(1) Base 10을 얻고, 자릿수는 그대로 둔 채 밑을 1 늘린 것입니다. 그다음 항은 (4)(0) Base 12, 즉 10진법으로 48입니다. 아래 표는 수열이 어떻게 이어지는지 보여 줍니다.

B	밑 B에서의 N	10진법 N	설명
10	(4)(2)	42	두 시작 수로 수열이 정의됩니다.
11	(4)(1)	$4 \times 11 + 1 = 45$
12	(4)(0)	$4 \times 12 + 0 = 48$
13	(3)(11)	$3 \times 13 + 11 = 50$	먼저 (이전 밑에서) 1을 빼고 나서 밑을 늘린다는 점에 유의하세요.
14	(3)(10)	$3 \times 14 + 10 = 52$
15	(3)(9)	$3 \times 15 + 9 = 54$

이렇게 계속 커질 것처럼 보이지만, 이 수열은 결국 밑 $B = 192$ 에서 0에 도달합니다(항이 (1) Base 191로, 그다음 (0) Base 192로 갑니다). 다음 표는 다른 시작점에 대한 수열을 보여 줍니다. 보다시피 값은 매우 빠르게 커질 수 있습니다(밑 100에서 항은 이미 1000707070428에 이릅니다).

B	밑 B에서의 N	10진법 N
2	(1)(1)(0)(0)(1)(0)(0)	100
3	(1)(1)(0)(0)(0)(1)(1)	976
4	(1)(1)(0)(0)(0)(1)(0)	5124
5	(1)(1)(0)(0)(0)(0)(3)	18753
6	(1)(1)(0)(0)(0)(0)(2)	54434
7	(1)(1)(0)(0)(0)(0)(1)	134457

나무수염은 이 수열이 처음에는 엄청나게 큰 값으로 치솟더라도 언제나 0에 도달한다고 설명합니다. 빌보는 이를 믿기 어려워하며 당신의 도움을 청합니다. 두 시작 수 $N$ 과 $B$ 가 주어질 때, 밑이 $2^{60}$ (빌보가 상상할 수 있는 거의 가장 큰 수)에 이르기 전에 수열이 0에 도달하는지, 도달한다면 어느 밑에서 0이 되는지 판정하세요.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어집니다( $T < 100$ ). 이어지는 $T$ 개의 각 줄에는 시작 수 $N$ 과 시작 밑 $B$ ( $B \ge 2$ )가 공백 하나로 구분되어 주어집니다.

출력

각 테스트 케이스마다 한 줄을 출력합니다. 밑이 $2^{60}$ 에 이르기 전에 수열이 0에 도달하면 다음을 출력합니다.

Starting with N = <N> and B = <B>, sequence converges to 0 at Base <base>.

여기서 <base>는 항이 처음으로 0이 되는 밑입니다. 그렇지 않으면 다음을 출력합니다.

Starting with N = <N> and B = <B>, sequence did not converge to 0 before 2^60.

예제1

예제 1

입력

예상 출력

Starting with N = 42 and B = 10, sequence converges to 0 at Base 192.
Starting with N = 100 and B = 2, sequence did not converge to 0 before 2^60.
Starting with N = 12 and B = 10, sequence converges to 0 at Base 24.
Starting with N = 15 and B = 8, sequence converges to 0 at Base 30.
Starting with N = 20 and B = 5, sequence converges to 0 at Base 80.