48. 프로젝트 오일러 #48 : 자체 제곱수

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

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

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

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

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