Problem26 1/d の中で循環節が最も長くなるd

問題

単位分数とは分子が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 を求めよ。

ソース

#include <stdio.h>
#include <vector>

struct defineOnePair
{
    int Syou;
    int Amari;
};

void main()
{
    std::vector<defineOnePair> OnePairVect;
    int MaxJyunkanVal = 0;
    int MaxJyunkan = 0;
    for (int I = 2; I < 1000; I++) {
        OnePairVect.clear();

        int Wararerukazu = 10;
        int Syou, Amari;

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

            int WKInd=-1;
            for(int P=0;P<=(int)OnePairVect.size()-1;P++){
                if(OnePairVect.at(P).Syou == WillAdd.Syou && OnePairVect.at(P).Amari == WillAdd.Amari){
                    WKInd = P;
                    break;
                }
            }
            if (WKInd >= 0) {
                int LenJyunkan = (int)OnePairVect.size() - WKInd;
                printf(" 循環部の長さ=%d",LenJyunkan);
                if (LenJyunkan > MaxJyunkan) {
                    MaxJyunkan = LenJyunkan;
                    MaxJyunkanVal = I;
                }
                break;
            }
            OnePairVect.push_back(WillAdd);

            if (FirstFlag) {
                FirstFlag = false;
                puts("");
                printf("1/%d=0.%d",I,Syou);
            }
            else{
                printf("%d",Syou);
            }
            Wararerukazu = Amari * 10;
        } while (Amari != 0);
    }
    puts("");
    printf("答えは、%dで、循環部の長さ=%d\n",MaxJyunkanVal, MaxJyunkan);
}

実行結果

省略
1/998=0.001002004008016032064128256513026052104208416833667334669338677354709418
83767535070140280561122244488977955911823647294589178356713426853707414829659318
63727454909819639278557114228456913827655310621242484969939879759519038076152304
60921843687374749498997995991983967935871743486973947895791583166332665330661322
64529058116232464929859719438877755511022044088176352705410821643286573146292585
17034068136272545090180360721442885771543086172344689378757515030060120240480961
923847695390781563126252505 循環部の長さ=498
1/999=0.001 循環部の長さ=3
答えは、983で、循環部の長さ=982

解説

STLのFindIndexメソッドは、ラムダ式が使えないと不便なので、For文で代用してます。