C#でプロジェクトオイラーを解く（問題２６「逆数の循環節 その1」）

Tweet

Pocket

どーも、みつおです。

循環節は「循環小数の循環節を求める」のサイトを参考にさせてもらいました！

循環節難しい。。。

問題

単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる.

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

0.1(6)は 0.166666… という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある.

d < 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ.

出典：Problem26

解答

using System;
using System.Collections.Generic;
using System.Linq;

namespace Problem26
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Solve());
            Console.ReadLine();

        }

        private static int Solve()
        {
            int ret = 0;
            int keta = 0;
            int maxketa = 0;

            // 1/d 1000未満に対してのループ
            for(int i = 2;i < 1000; i++)
            {
                //循環節数を求める
                keta = GetJunkansetu(i);

                //桁数の最大値を更新
                if (maxketa < keta)
                {
                    maxketa = keta;
                    ret = i;
                }
            }

            return ret;
        }

        private static int GetJunkansetu(int no)
        {
            int ret = 0;
            List<int> amarilist = new List<int>();
            int amari = 1;

            while(true)
            {
                //余りの数値を10倍する
                amari *= 10;

                //余りを求める
                amari = amari % no;

                //割り切れるなら終了
                if (amari == 0) break;

                //余りのリストに無ければ、追加。リストの中に見つかったら循環節
                if (!amarilist.Contains(amari)) amarilist.Add(amari);
                else break;
            }

            //桁数を求める
            ret = amarilist.Count();

            return ret;
        }
    }
}

出力

983