n 제곱의 자릿수가 n인 경우의 개수는?

 

짧고 간결한 프로젝트 오일러 문제 하나.

제목에서도 적었듯이 n제곱 해서 나온 숫자의 자릿수가 n인 모든 경우를 묻는 것이다.

다른 문제도 그렇지만, 이 문제는 일일이 제곱을 해가며 풀 수도 있다.

제곱의 결과가 64비트 범위를 넘어설 수도 있으니 이 부분을 해결할 아이디어만 있으면 된다.

 

하지만 그런 무식한(?) 방법보다는 로그를 활용하는 것이 훨씬 더 좋다.

 

일단 10진수 D의 자릿수가 n이라는 건 \(n-1 \leq log _{10} D \lt n\) 이라고 쓸 수 있다.

또한, 문제의 특성상 지수의 밑은 오로지 1~9 까지만 가능하다.

 

다시 말해서 \(1 \leq d \leq 9\) 인 자연수 d에 대해서 \(n-1 \leq log _{10} d ^ {n} \lt n\) 인 자연수 n의 개수를 세면 되는 것이다.

이 식은 로그의 특성을 고려하면 \(\frac {n-1}{n} \leq log _{10} d \lt 1\) 로 정리할 수 있다.

그런데, 애초에 \(log _{10}{ d }\) 는 1보다 작을 수밖에 없어 오른쪽 부등호는 없어도 된다.

 

이 내용을 그대로 코드로 표현하면 아래와 같다.

 

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int count = 0;
    for (int d = 1; d < 10; ++d) {
        double l10d = log10(d);
        
        for (int n = 1; ; ++n) {
            double ratio = (n - 1) / (double)n;
            if (ratio <= l10d) {
                cout << d << "^" << n << endl;
                ++count;
            }

            if (ratio > l10d) {
                break;
            }
        }
    }

    cout << count << "EA" << endl;
}

 

그런데, 조금만 생각해보면 안쪽 루프 자체를 제거해서 코드를 더 최적화할 수 있다.

 

\(\frac {n-1}{n} \leq log _{10} d\) 는 \(\frac {1}{n} \geq 1 - log _{10} d\) 로 정리하면 다시 \(n \leq \frac {1}{ 1 - log _{10} d}\) 로 정리할 수 있다.

여기서 n은 1 이상이어야 하므로 단순히 \(\left [ \frac {1}{ 1 - log _{10} d} \right ]\) 만 누적하면 똑같은 결과를 얻을 수 있다.

 

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int count = 0;
    for (int d = 1; d < 10; ++d) {
        double l10d = log10(d);

        int x = (int)(1.0 / (1 - l10d));
        cout << x << endl;
        count += (int)x;
    }

    cout << count << "EA" << endl;
}