Pongeponge

Project Euler : Problem 29 『Distinct powers』

犬と猫犬と猫 / kagawa_ymg

問題

projecteuler.net


 ab (2 ≤ a ≤ 100, 2 ≤ b ≤ 100) で作れる数は何個あるか?


値が大きいので極力計算しない方向で

 100100なんか計算してられないし。
何より、100100までの数字をチェックしないといけないなんて悪夢だ…。


重複を見る

 例えば、24 と 42 は共に16で重複してる。
なぜ重複してるのかというと、4 = 22なので、
42
= (22)2
= 22×2
= 24
 同じ底aで揃えた場合、同じ指数bになれば同じ数字だとわかる。
この場合、底と指数が違うのに計算結果が同じになるので、値のダブルチェックを回避する。


 ……とりあえず説明が凄くめんどくさいので、後はコードを見てください(手抜き)


コード
using System.Diagnostics;
using System.Linq;

namespace Problem29
{
    class Program
    {
        //範囲
        static int min = 2;
        static int max = 100;

        static void Main(string[] args)
        {
            Debug.WriteLine(DistinctPowers());
        }

        static int DistinctPowers()
        {
            bool[] findA = new bool[max + 1];
            int sum = 0;

            for (int a = min; a <= max; a++)
            {
                if (findA[a] == false)
                {
                    int b = maxB(a, findA);

                    sum += NumberCount(b);
                }
            }

            return sum;
        }

        /// <summary>
        /// a^bの最も大きいbを調べる
        /// </summary>
        static int maxB(int a, bool[] findA)
        {
            int b = 0;

            for (int i = a; i <= max; i *= a)
            {
                findA[i] = true;
                b++;
            }

            return b;
        }

        /// <summary>
        /// b乗まである場合の出現個数を求める
        /// </summary>
        static int NumberCount(int b)
        {
            if (b == 1) return max - min + 1;

            bool[] findB = new bool[b * max + 1];

            for (int d = 1; d <= b; d++)
            {
                for (int j = min * d; j <= d * max; j += d)
                {
                    if (findB[j] == false) findB[j] = true;
                }
            }

            return findB.Where(obj => obj == true).Count();
        }
    }
}
結果

 9183


 ホント説明しにくいわ…。
ホワイトボードなんかで対話的にバーッと書いてやれるんならどれだけラクか。



指数で儲けるカンタン売買

指数で儲けるカンタン売買

EQ こころの知能指数 (講談社+α文庫)

EQ こころの知能指数 (講談社+α文庫)