TEUS.me

 
 


문제는 간단하다. 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 클래스를 한번 만들어봐야겠다… 근데, 나누기는 어떻게 하지? ㄷㄷㄷㄷ



공유하기

facebook twitter kakaoTalk kakaostory naver band

댓글

비밀글모드

  1. 나누기.
    1. 그냥 뺀다. (효율 극악)
    2. 쉬프트 한다.
    a / 2 = a / 10(2진수)
    젯수의 마지막 자리가 0 이므로 계산 안 함.
    젯수 쉬프트 하면, 마지막 자리가 1 이므로 계산. (피젯수를 쉬프트)
    이런 식으로 해야 하는데, 이것도 상당히 노가다입니다. (중간에 처리할 일이 좀 많습니다.)

    2014.10.27 20:27