Project Euler : Problem 16 『Power digit sum』

Math / Silenceofnight

projecteuler.net

問題

　2¹⁰⁰⁰の各桁を全て足し合わせた数を求めよ。

うーん……

　結局、2¹⁰⁰⁰を計算して桁ごとに足していくしかないんだろうか？
どうにもいい方法を思いつかない。

なら計算回数減らす方向で

　2を1000回掛け算するよりも
2を10回掛ける　→　2¹⁰
2¹⁰を10回掛ける　→　2¹⁰⁰
2¹⁰⁰を10回掛ける　→　2¹⁰⁰⁰
こうすれば30回で済む。

コード

using System.Diagnostics;
using System.Numerics;

namespace Problem16
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(Result());
        }

        static BigInteger Result()
        {
            string str = Power(Power(Power(2, 10), 10), 10).ToString();

            return DigitSum(str);
        }

        /// <summary>
        /// xのy乗を求める
        /// </summary>
        static BigInteger Power(BigInteger x, BigInteger y)
        {
            BigInteger n = 1;
            for (int i = 0; i < y; i++)
            {
                n *= x;
            }

            return n;
        }

        /// <summary>
        /// 各桁の総和を求める
        /// </summary>
        static int DigitSum(string s)
        {
            int n = 0;

            foreach (char c in s)
            {
                n += (c - '0');
            }

            return n;
        }
    }
}