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

 

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

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

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

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

 

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

 

일단 10진수 D의 자릿수가 n이라는 건 $n-1\le lo{g}_{10}D<n$ 이라고 쓸 수 있다.

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

 

다시 말해서 $1\le d\le 9$ 인 자연수 d에 대해서 $n-1\le lo{g}_{10}{d}^n<n$ 인 자연수 n의 개수를 세면 되는 것이다.

이 식은 로그의 특성을 고려하면 $\frac{n-1}{n}\le lo{g}_{10}d<1$ 로 정리할 수 있다.

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

 

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

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#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}\le lo{g}_{10}d$ 는 $\frac{1}{n}\ge 1-lo{g}_{10}d$ 로 정리하면 다시 $n\le \frac{1}{1-lo{g}_{10}d}$ 로 정리할 수 있다.

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

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#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; }