100!의 각 자리수의 총합은? (프로젝트 오일러 #20)

문제는 간단하다. 100!을 계산해서 각 자리수의 합을 구하는 것.

이게 대체 몇 자리나 되는지를 간단히 알아보기 위해 계산기를 돌려봤다.

158자리 숫자… 대체 어떻게 읽어야 되는 건가…

9.3326....E+157이니까 158자리 숫자다.

당연한 얘기지만, long long int 같은 건 아이고 의미 없다…

앞으로도 계속 써먹기 위해 CBigInt 같은 클래스를 하나 만들어볼까 하다가 그냥 간단히 만드는 것으로 방향 전환…

팩토리얼은 승수와 피승수가 모두 큰 정수일 필요가 없기 때문에 최대한 간단히 만들어봤다.

#include <cstdio>
#include <cstdlib>
#include <cmath>

// 각 자리에 0~9999를 저장하는 것으로...
// 즉 10000진수 개념을 적용
const unsigned nDigit = 10000;

unsigned *assign(int data, int &len)
{
    // 입력값은 1 이상이니까 대충 작성…
    len = int(log(data) / log(nDigit) + 1);
    unsigned *ret = new unsigned[len];
    for (int i = 0; i < len; i++) {
        ret[i] = data % nDigit;
        data /= nDigit;
    }

    return ret;
}

unsigned *multiply(unsigned *num1, int len1, int numMul, int &lenRet)
{
    unsigned *ret = new unsigned[len1 + 1];
    for (int i = 0; i < len1; i++) {
        ret[i] = num1[i] * numMul;
    }
    ret[len1] = 0;

    for (int i = 0; i < len1; i++) {
        ret[i + 1] += (ret[i] / nDigit);
        ret[i] %= nDigit;
    }

    lenRet = len1;
    if (ret[len1]) lenRet++;

    return ret;
}

int getSumOfAllDigits(unsigned *num, int len)
{
    int sum = 0;
    for (int i = 0; i < len; i++) {
        unsigned temp = num[i];
        while (temp) {
            sum += temp % 10;
            temp /= 10;
        }
    }
    return sum;
}

void printfnum(unsigned *num, int len, bool enter) {
    for (int i = len - 1; i >= 0; i--) {
        printf(((i == len - 1) ? "%d" : "%04d"), num[i], num[i]);
    }
    if (enter) {
        printf("\n");
    }
}

int main(int argc, char* argv[])
{
    int len1, len2;
    unsigned *num1, *num2;

    num1 = assign(1, len1);
    for (int i = 2; i <= 100; i++) {
        num2 = multiply(num1, len1, i, len2);
        delete num1;

        num1 = num2;
        len1 = len2;
    }

    printfnum(num1, len1, true);

    printf("sum of digits: %d\n", getSumOfAllDigits(num1, len1));

    delete num1;
    return 0;
}

실행 결과는 아래와 같다…

계산기로 확인한 대로 158자리가 맞으며, 앞부분도 일치한다.

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
sum of digits: 648

덧. 조만간 큰 정수를 처리하기 위한 CBigInt 클래스를 한번 만들어봐야겠다… 근데, 나누기는 어떻게 하지? ㄷㄷㄷㄷ