ProjectEuler29

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Numerics;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler29
{
    class MainClass
    {
        /*
         * 2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, a^bを全て考えてみよう:
         * 
         * 2^2=4, 2^3=8, 2^4=16, 2^5=32
         * 3^2=9, 3^3=27, 3^4=81, 3^5=243
         * 4^2=16, 4^3=64, 4^4=256, 4^5=1024
         * 5^2=25, 5^3=125, 5^4=625, 5^5=3125
         * これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:
         * 
         * 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
         * 
         * 2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか?
         */
        const int MIN_AB = 2;
        const int MAX_AB = 100;
        static readonly int NUM_AB = MAX_AB - MIN_AB + 1;
        public static void Main(string[] args)
        {
            MeasureTime("CountAll", CountAll); // Method1
            MeasureTime("Count_ConsideringDuplication", Count_ConsideringDuplication); // Method2
        }

        // Method1: Calculate all value and remove duplication
        public static void CountAll()
        {
            HashSet<BigInteger> valSet = new HashSet<BigInteger> ();
            for (int a = MIN_AB; a <= MAX_AB; a++) {
                for (int b = MIN_AB; b <= MAX_AB; b++) {
                    valSet.Add(BigInteger.Pow(a, b));
                }
            }

            Console.WriteLine(valSet.Count);
        }

        // Method2: アルゴリズムをソース最後に示す
        public static void Count_ConsideringDuplication()
        {
            SortedList<int, int> powList = new SortedList<int, int> ();
            int counter = 0;

            for (int a = MIN_AB; a <= MAX_AB; a++) {
                if (powList.ContainsKey(a)) {
                    counter += NUM_AB - calcDupNum(powList[a]);
                }
                else {
                    counter += NUM_AB;

                    int t = 2;
                    int pow = a * a;
                    while (pow <= MAX_AB) {
                        powList[pow] = t;
                        ++t;
                        pow *= a;
                    }
                }
            }

            Console.WriteLine(counter);
        }

        // (k=exponent) a^1,a^2,...,a^(k-1)との重複するインデックスの和集合の要素数, memorizable
        public static int calcDupNum(int exponent)
        {
            HashSet<int> set = new HashSet<int>();
            for (int i = 1; i < exponent; i++) {
                int g = gcd(exponent, i);
                int num = 100 * g / exponent;

                set.UnionWith(Enumerable.Range(1, num).Select(val => (i / g) * val).Where(val => val != 1));
            }
            return set.Count;
        }

        // utility method to measure time
        public static void MeasureTime(string description, Action method)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            method();
            sw.Stop();
            Console.WriteLine(string.Format("{0}:{1}ms", description, sw.ElapsedMilliseconds));
        }

        // greatest common divisor
        public static int gcd(int a, int b)
        {
            if (a < b) { return gcd(b, a); }
            int c;
            while( b != 0 ) {
                c = a % b;
                a = b;
                b = c;
            }
            return a;
        }
    }
}

/*
 * 考え
 * 2つの数a,bがa=k^i, k^j(k,i,j:自然数)と表せない時，a^n, b^m(2<=n,m<=100)は重複することはない(素因数とか考えたら自明)．
 * つまり，重複する場合が存在するのはある2つの数a,bがa=k^i, b=k^j(k,i,j:自然数)と表せる時．
 * 例えば，k=2の時を考えると，2^x, 4^y, 8^z,...,64^n(指数は[2,100])は各々重複が存在する．
 * 
 * (a^k)^n, (a^l)^m(2<=n,m<=100)の重複を考えると，kn=lmとなる場合全てが重複する場合．
 * これは，k<l, g = gcd(k,l)とすると，mについて，[ (k/g)*x | x<-[1,2,...,(100*g)/l], (k/g)*x != 1]となる時にあるnについて重複が存在する．
 * (整数同士の/記号は小数点以下切り捨て)
 * 
 * よって，要素の重複を除く要素のカウントのアルゴリズムは以下
 *
 * カウンタを0に初期化
 * i=2から100まで以下を実行
 * -iがa^kと表せない場合には，カウンタに99([2,100].Length)を追加
 * -iがa^kと表せる場合には，a^1,a^2,...,a^(k-1)との重複するインデックスの和集合の要素数を求め，99からその要素数を引いた値をカウンタに追加
 */


// 9183
// CountAll:156ms
// 9183
// Count_ConsideringDuplication:14ms