이 문제를 읽은 뒤, 가능한 N의 개수는 1000 종류 이므로 T 또한 최대 1000 까지 들어올 것이라고 예상하고 제출한 프로그램이 시간 초과를 받았습니다.

N이 주어지면, 2진법부터 N진법까지 끝자리에 0이 나오지 않을 때 까지 계속 나누는 단순한 방법 O(n log n) 으로 작성했습니다.

N이 충분히 작기 때문에 이 방법으로도 충분히 풀 것이라고 생각했으며, T 또한 '상식적인' 범위 라고 생각했었습니다.

핵심 알고리즘은 그대로 둔 채, 가능한 모든 N값에 대해 미리 계산하는 방법으로 '맞았습니다'를 받긴 했습니다만, 이 문제의 입력 데이터가 부당하다는 생각은 여전합니다.

(첨부판 소스 파일은 이 방법을 적용하기 전의 프로그램으로, 시간 초과를 받은 프로그램입니다.)

만약 이 문제의 의도가 소인수분해 같은 좀 더 효율적인 알고리즘을 작성하는 것이었다면, 억지로 T를 늘리는 대신에 N의 범위를 조절하는 것이 합당하다고 생각합니다.