Pongeponge

Project Euler : Problem 16 『Power digit sum』

MathMath / Silenceofnight
projecteuler.net


問題

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


うーん……

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


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

 2を1000回掛け算するよりも
2を10回掛ける → 210
210を10回掛ける → 2100
2100を10回掛ける → 21000
こうすれば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;
        }
    }
}
解答

 1366


 基数と乗数からペペペと桁の総和が出ればなぁ……。