챔퍼나운(Champernowne) 상수의 특정 자리 숫자는? (프로젝트 오일러 #40)

정규수(Normal number)라는 개념이 있다.

그리고, 극단적인 정규수로 챔퍼나운 상수(Champernowne's constant)가 있다.

이 문제는 챔퍼나운 상수의 1, 10, 100, 1000, 10000, 100000, 1000000 자리 숫자의 곱을 구하는 문제다.

근데, 정규수와 챔퍼나운 상수의 수학적 의미와 별개로 이 문제는 숫자만 나열하면 되는 문제라 의외로 쉽다.

처음부터 일일이 다 늘어놓는 방법도 있지만, 그건 좀 심하고, 조금만 생각을 해보면 계산을 많이 줄일 수 있다.

1. 1~9자리는 그대로 1~9임

2. 10~99의 90개는 2자리임

3. 100~999의 900개는 3자리임, 이후도 같은 규칙임

이런 규칙들을 염두에 두면 대략 아래와 같은 코드가 나온다.

?

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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <cstdio> #include <cmath>   unsigned nDigitBegin(unsigned digit) {     unsigned count = 1;     for (unsigned i = 1; i < digit; i++) {         count *= 10;     }     return count; }   unsigned getNthDigit(unsigned n) {     if (n < 10) return n;     // 1~9 : 1자리     // 10~99: 2자리 (90개)     // 100~999: 3자리 (900개)       // 이 sum은 자리수의 합을 의미함. 숫자의 합이 아님     unsigned sum = 9;     unsigned digit = 1;     while (sum < n) {         digit++;         sum += digit * 9 * nDigitBegin(digit);     }       // 결과는 digit 자리 내에 있음     // 한 자리 백     sum -= digit * 9 * nDigitBegin(digit);     // 현재까지의 자리수의 합은 sum       unsigned from = nDigitBegin(digit);     // 숫자는 from 부터 시작함       int count = (n - sum - 1) / digit;     // 현재부터 count개 다음에 시작된다는 뜻임       sum += digit*count;     from += count;       static char str[10];     sprintf_s(str, 10, "%u", from);       return (str[n-sum-1]-'0'); }   int main(int argc, char* argv[]) {     printf("-= Champernowne's constant =-\n");     unsigned product = 1;     for (unsigned i = 0, digit = 1; i < 7; i++, digit *= 10) {         unsigned nthDigit = getNthDigit(digit);         printf("d(%u) = %u\n", digit, nthDigit);         product *= nthDigit;     }     printf("product = %u\n", product);     return 0; }

결과는 아래와 같다.

?

1 2 3 4 5 6 7 8 9

-= Champernowne's constant =- d(1) = 1 d(10) = 1 d(100) = 5 d(1000) = 3 d(10000) = 7 d(100000) = 2 d(1000000) = 1 product = 210