Problem 16

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¹⁰⁰⁰?

 

とりあえず、力づくで解く前に少し考察してみる

 

 

要は3000桁を超えるでっけえ数字になるということだ

つまり、2の1000乗を計算→各桁の数字を足していく方法でもよいが、

少し工夫を凝らして見ることにした。

 

掛け算、ここでは累乗の「車輪の再発明」を行った

math.pow(n,m)

を自分で文字列として具体的な数字としてすべての桁を返すクラスを作成した。

        public static string very_big_pow(int a, int n)
{
//桁数を求める
int d = (int)Math.Ceiling(Math.Log10(a)*n);

//初期化
byte[] digits = new byte[d];
byte[] digitsp = new byte[d];
byte[] fdigits = new byte[a.ToString().Length];
int fdigitsn = a.ToString().Length - 1;
int ndigitsn = fdigitsn;

fdigits[0] = byte.Parse(a.ToString().Substring(0, 1));
for (int i = 0; i <= fdigitsn; ++i)
{
fdigits[i] = byte.Parse(a.ToString().Substring(fdigitsn - i, 1));
digits[i] = byte.Parse(a.ToString().Substring(fdigitsn - i, 1));
}

for (int i = 2; i <= n; ++i)
{
for (int j = 0; j <= d-1; ++j)
{
digitsp[j] = digits[j];
digits[j] = 0;
}
for (int j = d - 1; digitsp[j] == 0; --j)
{
ndigitsn = j;
}
for (int j = 0; j <= fdigitsn; ++j)
{
for (int k = 0; k <= ndigitsn; ++k)
{
digits[k + j] += (byte)(digitsp[k] * fdigits[j]);
}
for (int k = 0; k <= ndigitsn; ++k)
{
if (digits[k] >= 10)
{
digits[k + 1] += (byte)(digits[k]/ 10);
digits[k] = (byte)(digits[k] - (byte)(digits[k] / 10) * 10);
}
}
}
}
string result = "";
for (int k = 0; k <= d -1 ; ++k)
{
result = digits[k].ToString()+result;
}
return result;
}

具体的なアルゴリズムとしては、まずは先に書いた対数の利用で累乗結果の桁数を求める

後は、小学校高学年で習ったアルゴリズムを利用して計算を行なっているだけ。

小学校の時にかわいがってくださった先生、ありがとうございます。

 

利用例

            //巨大な累乗
int ans = 0;
string root = stat.very_big_pow(2, 1000);
Console.WriteLine(root);
for (int k = 0; k <= root.Length - 1; ++k)
{
ans += int.Parse(root.Substring(k, 1));
}
Console.WriteLine(ans.ToString());