[SCPC] 13번: 균일수

[SCPC] 13번: 균일수

자연수를 표시하기 위한 표기법으로는 10을 기저로 하는 10진법을 가장 많이 사용한다.

하지만, 그 이외에도 어떤 자연수이든지 기저로 하여 표현하는 것이 가능하다.
예를 들어 10을 기저로 하는 10진법에서 238로 표현되는 수가, 2를 기저로 하는 2진법에서는 11101110으로 표현된다.

그리고, 같은 수를 23진법으로 표현하면 10, 8로 표현될 것이다. (23진법에서는 각 자리수는 10진수로 표현하고 자리수 사이를 콤마로 구분하였다. 기저가 10 이상인 경우에만 이렇게 콤마로 구분하는 방법을 쓴다.)

자연수 N이 기저 b에 대한 b진법으로 표현했을 때 모든 자리수의 값이 같게 되는 경우 N을 b에 대해서 “균일수”라고 부른다.

예를 들어, 10진수 36은 기저 17에 대해서 2,2로 표현되므로, 10진수 36은 17에 대해서 균일수가 되고, 10진수 36은 또한 기저 8에 대해서도 균일수가 된다. 그 이유는 10진수 36의 8진수 표현이 44이기 때문이다.

자연수 N이 하나 이상의 기저에 대해 균일수가 된다면, 그 기저들 중 가장 작은 값을 구하려고 한다. 극단적인 경우, 만약 b>N이라면 N은 b진법으로 한자리 수가 되는데, 이 때도 균일수가 되는 것으로 간주한다.

자연수 N이 주어졌을 때, N이 b에 대해서 균일수가 되는 최소의 양의 정수 b를 구하는 프로그램을 작성하시오. 단, b 는 2 이상이어야 한다.

메모리 사용 제한

• heap, global, static (총계) : 256MB
• stack : 1MB

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫 번째 줄에 테스트 케이스 개수를 나타내는 자연수 T가 주어지고, 이후 차례로 T개의 테스트 케이스가 주어진다. ( 1≤T≤100 )

두 번째 줄부터 주어지는 각각의 테스트 케이스는 자연수 N으로 주어진다. ( 1≤N≤109 )

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에 “Case #T”를 출력하여야 한다. 이때 T는 테스트 케이스의 번호이다.

그 다음 줄에는 N이 b에 대해서 균일수가 되는 최소 양수 b를 출력한다. 단, b는 2이상이다.

입출력예

입력

2
36
127

출력

Case #1
8
Case #2
2

풀이

일반적인 진법 변환으로 시도하게 되면 N=999999996 등 큰 수가 주어졌을 때 이를 1초 안에 계산하지 못합니다.

진법이 충분히 커지면 1024, 1024와 같은 식으로 두 자리 숫자가 된다는 점을 포착하여 문제를 해결했습니다. 이때 식은 다음과 같습니다.

𝑏𝑎𝑠𝑒 = 𝑛𝑢𝑚 / 𝑎 − 1

𝑛𝑢𝑚 = 𝑎 ∗ 𝑏𝑎𝑠𝑒 + 𝑎

n진법의 각 자리수는 n보다 작아야하기 때문에 다음이 성립합니다.

𝑎 < 𝑏𝑎𝑠𝑒 = 𝑛𝑢𝑚 / 𝑎 − 1

𝑎*𝑎 < 𝑛𝑢𝑚 − 𝑎

a는 0 이상, num은 1 이상이기 때문에

𝑎 < −1 + sqrt(1 + 4𝑛𝑢𝑚) < sqrt(𝑛𝑢𝑚)

#include <cmath>
#include <iostream>

using namespace std;

// 진법 변환
bool convertBase(int base, int num) {
  int mod = num % base;
  num /= base;

  while (num != 0) {
    if (mod != num % base)
      return false;
    num /= base;
  }
  return true;
}

int main(int argc, char** argv) {

  int answer, num, T; cin >> T;

  for (int tn=0; tn<T; tn++) {

    cin >> num;
    // 최악의 경우
    answer = num - 1;

    // 예외
    if (num == 2) {
      cout << "Case #" << tn+1 << endl;
      cout << 3 << endl;
      continue;
    }

    // 큰 수 처리
    // 11, 22, 33, ... 식의 수가 성립하는 경우를 찾는다.
    // num = (num/base - 1) * base + base
    int past_i = 1;
    int max_base = sqrt(double(num));
    for (int i=max_base-1; i>=1; i--) {
      if (num % i == 0) {
        answer = num / i - 1; // answer = base입니다.
        break;
      }
    }

    // 2진법부터 올라가며 체크
    for (int base=2; base<=max_base+1; base++) {
      if (convertBase(base, num)) {
        answer = base;
        break;
      }
    }

    // 출력
    cout << "Case #" << tn+1 << endl;
    cout << answer << endl;
  }

  return 0;
}