[C/C++] 프로젝트 오일러 #48 : 자체 제곱수

이번 문제도 쉬운 문제입니다.

내용도 상당히 짧습니다.  난이도는 5%입니다.

 

Project Euler 문제 48번 “Self Powers”는 1부터  n 까지의 자연수 각각을 그 수만큼 거듭제곱한 후, 이 값을 모두 더한 결과의 마지막 10자리를 구하는 문제입니다. 즉, 다음과 같은 수식을 계산합니다.

\[1^1 + 2^2 + 3^3 + \dots + n^n\]

이 합의 결과는 매우 클 수 있으므로, 마지막 10자리만을 구하는 것이 핵심입니다. 일반적인 정수형 변수로는 이 값을 직접 저장하기 어렵기 때문에, 모듈로 연산을 활용하여 마지막 10자리를 유지하면서 계산하는 것이 필요합니다.

입력값으로는  n 이 주어지며, 문제에서 기본적으로  n = 1000 인 경우를 고려합니다. 따라서, \( 1^{1} + 2^{2} + … + 1000^{1000}\) 의 합을 구하고, 그 값의 마지막 10자리를 출력하면 됩니다.

 

이 문제에서 핵심이 되는 내용은 바로 결과물의 아래 열자리만 구하라는 것입니다.  그렇지 않다면, 사실 일반 프로그래밍 언어의 정수형 변수로는 계산할 수가 없습니다.  1000의 1000승이면, 0이 3000개나 되고요.  이진수로 표현하려면 10,000비트(1,250바이트)정도가 필요합니다.

 

자체 제곱을 하는데 있어서 좀 더 유연하게 할 수는 있습니다.  예를 들어서 2의 8승을 구하기 위해서는 2의 4승을 구해서 제곱을 하면 되겠죠.  이런 식으로 지수의 곱을 줄여줄 수 있지만, 그런 고급 기법은 암호화 알고리즘에서나 쓰면 됩니다.  암호화 알고리즘에서는 수억, 수천억제곱보다 더 한 것들을 합니다.  512비트를 쓴다면, 10의 153승에 해당하는 제곱을 하겠죠.  이 경우 순차적으로 곱해주는 알고리즘으로는 절대 원하는 값을 얻을 수 없습니다.  그래서 곱하는 횟수를 줄여주는 알고리즘이 필요하겠지만, 이 문제는 기껏해야 1,000승입니다.  그래서 단순무식한 방법으로 프로그램을 해보았습니다.

self powers

아래는 제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #48 - Self Powers
//        - by Aubrey Choi
//        - created at 2015-03-30
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

#define    DIV    10000000000

int main()
{
    uint64_t ans = 0;

    for( int i = 1 ; i <= 1000 ; i++ )
    {
        uint64_t m = 1;
        uint64_t s = i;

        for( int j = 0 ; j < i ; j++ )
        {
            m *= s;
            m %= DIV;
        }

        ans += m;
        ans %= DIV;
    }
    printf("ans = %ju\n", ans);
}