[Algorithm] 로그를 사용하여 큰 수의 자릿수 계산하기

로그를 사용하면 곱셈을 덧셈으로 변환할 수 있기 때문에 큰 수의 자릿수를 효율적으로 구할 수 있다.

그러나 로그를 사용하는 것은 정확한 값이 아닌 자릿수만 구하는 경우에만 유용하다.

 

로그를 이용한 자릿수 계산

수의 자릿수를 구하기 위해서는 그 수가 10의 몇 승에 가까운지를 알아내야 한다.

예를 들어 100은 $10^{2}$이므로 3자리 숫자이고, 9999는 $10^{3.X...}$ 이므로 4자리 숫자이다.

수 N의 자릿수를 구하는 방법은 다음과 같다.

자릿수 =  $ \left \lfloor log10​(N) \right \rfloor+1 $

이 원리를 사용하여 곱셈 연산을 로그의 덧셈으로 바꿀 수 있다.

 

예시

백준 12179

아래에 쓰여있는 문제를 읽기보다 링크에 들어가 예제와 힌트를 읽는게 문제를 이해하기 훨씬 쉽다.

최대 값인 9000!은 unsigned long long int를 사용해도 오버플로우가 발생하기 때문에, $log_{10}$을 통해 자릿수만 구한 뒤 벡터에 저장하고 꺼내서 답을 내는 방식으로 문제를 해결하였다.

Power Levels (Large) 성공다국어
 
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
5 초	512 MB	75	56	48	76.190%

문제
멀티팩토리얼, 즉 어떤 숫자 N 뒤에 0이 아닌 숫자 E개의 느낌표가 따라오는 수는, K가 0 이상의 정수일 때 (N - K*E)인 모든 양의 숫자들의 곱으로 정의된다. 일반적인 팩토리얼도 멀티팩토리얼의 정의에 맞는데, 예를 들어:
5! = 5 * (5-1) * (5-2) * (5-3) * (5-4) = 120

다음은 5의 다른 멀티팩토리얼들이다:
5!!는 5 * (5-2) * (5-4) = 15이다.
5!!!는 5 * (5-3) = 10이다.
5!!!!는 5 * (5-4) = 5이다.
5 뒤에 다섯 개 이상의 느낌표가 따라올 때는 5이다.
느낌표가 없는 5는 멀티팩토리얼로 간주되지 않는다.

악당 애니마와 그녀의 부하 미네라는 세 가지를 좋아한다: 멀티팩토리얼, "IT'S OVER 9000"을 외치는 것, 그리고 우주를 돌아다니며 싸울 상대를 찾는 것이다.
애니마와 미네라는 잠재적인 상대를 마주치면, 애니마는 미네라에게 상대의 파워 레벨을 측정하도록 요청한다. 파워 레벨은 항상 0으로 시작하지 않는 양의 정수이다. 오늘, 미네라의 스캐너가 흐릿해서, 그녀는 애니마에게 상대의 파워 레벨이 몇 자릿수인지만 알려줄 수 있고, 그 숫자가 무엇인지는 알 수 없다.
애니마는 상대의 파워 레벨을 정확하게 묘사하기 위해 9000의 멀티팩토리얼을 뒤따라 "IT'S OVER"라고 외치고 싶어 한다. 그녀는 결코 틀린 말을 하지 않을 것이며, 필요한 것보다 더 많은 느낌표를 사용하지 않는다. 예를 들어, D = 31682일 경우, 애니마는 "IT'S OVER 9000!"을 외칠 수 없다. 왜냐하면 9000!도 31682 자릿수를 가지며, 상대의 파워 레벨이 31682 자릿수 이하의 숫자일 수도 있기 때문이다. 그러나 9000!!는 31682 자릿수보다 적은 자릿수를 가지므로, "IT'S OVER 9000!!"은 확실히 사실일 수 있다. 상대의 파워 레벨이 분명 9000!!!, 9000!!!! 등보다 크다는 것도 알 수 있지만, 그녀는 필요한 것보다 더 많은 느낌표를 사용하지 않을 것이다. 따라서, 이 경우 애니마는 "IT'S OVER 9000!!"을 외친다.
만약 9000의 어떤 멀티팩토리얼도 상대의 파워 레벨보다 확실히 작지 않다면, 애니마는 극적으로 침묵을 지킬 것이다. 우리는 극적인 침묵을 ...으로 나타낸다.

애니마는 무엇을 외쳐야 하는가?

입력
입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. T개의 줄이 뒤따른다. 각 줄은 상대의 파워 레벨 자릿수인 양의 정수 D를 나타낸다.

제한사항
T = 19.
1 ≤ D ≤ 19.

출력
각 테스트 케이스에 대해 "Case #x: y" 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 애니마가 침묵해야 하는 경우 ...이거나, "IT'S OVER 9000" 뒤에 일정한 수의 느낌표를 붙인 문자열이다. 출력이 이 명세와 정확히 일치하도록 해야 한다. 아포스트로피 문자를 복사하여 유니코드 문제를 피하는 것이 좋다.

정답
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> calculate_multifactorial_digits(int max_exclamations) {
  vector<int> digits(max_exclamations + 1, 0);
  long long num = 9000;
  for (int e = 1; e <= max_exclamations; e++) {
    long double log_sum = 0;
    for (long long i = 9000; i > 0; i -= e) {
      log_sum += log10(i);
    }
    digits[e] = (int)log_sum + 1;
  }
  return digits;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  const int MAX_EXCLAMATIONS = 9000;
  vector<int> multifactorial_digits =
      calculate_multifactorial_digits(MAX_EXCLAMATIONS);

  int n;
  cin >> n;

  for (int i = 0; i < n; i++) {
    int t;
    cin >> t;

    string result = "...";
    for (int e = 1; e <= MAX_EXCLAMATIONS; e++) {
      if (multifactorial_digits[e] < t) {
        result = "IT'S OVER 9000";
        result += string(e, '!');
        break;
      }
    }

    cout << "Case #" << i + 1 << ": " << result << '\n';
  }

  return 0;
}