Problem417 逆数の循環節 その2

問題

単位分数とは分子が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桁ある.

分母が 2 および 5 の素因数だけからなるとき,
その単位分数は循環節を持たないと考えられる.
そのような単位分数の循環節の長さは 0 であるとしよう.

1/n の循環節の長さを L(n) で表すとしよう.

3 <= n <= 1000000   における、シグマL(n) は 55535191115 である.
3 <= n <= 100000000 における、シグマL(n) を求めよ.

ソース

using System;
using System.Collections.Generic;

class Program
{
    static bool HasJyunkansetu(int pBunbo)
    {
        while (pBunbo % 2 == 0) pBunbo /= 2;
        while (pBunbo % 5 == 0) pBunbo /= 5;
        return pBunbo != 1;
    }

    private struct defineOnePair
    {
        internal int Syou;
        internal int Amari;
    }

    static int DeriveLenJyunkan(int pBunbo)
    {
        var OnePairList = new List<defineOnePair>();

        int Wararerukazu = 10;
        int Syou, Amari;

        //bool FirstFlag = true;
        do {
            Syou = Wararerukazu / pBunbo;
            Amari = Wararerukazu % pBunbo;
            defineOnePair WillAdd;
            WillAdd.Syou = Syou; WillAdd.Amari = Amari;

            if (OnePairList.Contains(WillAdd)) {
                int WkInd = OnePairList.FindIndex(X => X.Syou == WillAdd.Syou
                                                && X.Amari == WillAdd.Amari);
                return OnePairList.Count - WkInd;
            }
            OnePairList.Add(WillAdd);

            //if (FirstFlag) {
            //    FirstFlag = false;
            //    Console.Write("1/{0}=0.{1}", pBunbo, Syou);
            //}
            //else Console.Write(Syou);

            Wararerukazu = Amari * 10;
        } while (Amari != 0);
        return 0;
    }

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        long AnswerLen = 0;
        for (int I = 3; I <= 1000000; I++) {
            if (HasJyunkansetu(I) == false) {
                //Console.WriteLine("1/{0}は、循環節を持ちません", I);
            }
            else {
                int LenJyunkan = DeriveLenJyunkan(I);
                //Console.WriteLine();
                //Console.WriteLine("1/{0}の循環節の長さは{1}", I,LenJyunkan);
                AnswerLen += LenJyunkan;
            }
            if (I % 1000 == 1)
                Console.WriteLine("{0}。{1}までの循環節の長さの合計={2}", sw.Elapsed, I, AnswerLen);
        }
    }
}

実行結果

計算量が多すぎるので、作り直しが必要です。

解説

答え 446572970925740