# 2^1000 의 각 자릿수별 합은 무엇인가?

일단 문제는 아래와 같다.

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

문제는 2^1000 의 값은 1.07150860718626732094842504906e+301 자릿수만해도 300자리 가까이 되는 매우 큰 수 라는점이다. 컴파일러에서 제공하는 자료형으로 이만큼 큰 수를 저장할 수 없다. 음.. 그렇다면 어떤 방법들이 있을까. 우선, 간단한 방법으로 해결은 했다. 메모리 낭비가 있지만, 자릿수 크기로 배열을 선언하고 이를 이용해 2의 n 승을 구한다. 답안 제출 후 Post에 있는 여러 해결방안을 보니 비슷하긴 하다. 음... 뭔가 획기적인 방법이 없을까? p.s. 큰수를 다루는걸로 구글링을 하다보니 재미난 글들이 많았다. http://bytes.com/topic/algorithms/insights/886822-calculating-large-exponents https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation

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

#include <iostream> #include <Windows.h> using namespace std; #define MAX_POW 1000 void main() { int digitArr[1024] = { 0 }; digitArr[0] = 2; int overFlow = 0; for (int pow = 1; pow <= MAX_POW - 1; ++pow) for (int arr_idx = 0; arr_idx < 1024; ++arr_idx) { if (overFlow == 1) { digitArr[arr_idx] *= 2; digitArr[arr_idx] += 1; overFlow = 0; } else { digitArr[arr_idx] *= 2; } if (digitArr[arr_idx] >= 10) { overFlow = 1; digitArr[arr_idx] %= 10; } } int sum = 0; for (int arr_idx = 0; arr_idx < 1024; ++arr_idx) sum += digitArr[arr_idx]; cout << sum << endl; system("pause"); }