Problem26

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

#define NUM 1000

typedef struct
{
    int e;
    int d;
} frac;

bool
isBreak(vector<frac> *pv, frac *fc)
{
    bool f = false;

    for (vector<frac>::iterator it = pv->begin(), end = pv->end(); it != end; it++)
    {
        if (it->e == fc->e && it->d == fc->d)
        {
            f = true;
            break;
        }
    }

    if (pv->empty())
    {
        f = false;
    }
    
    return f;
}

int
main(int argc, char **argv)
{
    int ans = -1;
    vector<frac>::size_type l = 0;
    int e, d; // 分子，分母

    for (int i = 2; i < NUM; i++)
    {
        e = 1;
        d = i;
        vector<frac> v;

        while (1)
        {
            frac fc;
            fc.e = e;
            fc.d = d;
            
            if (isBreak(&v, &fc))
            {
                break;
            }
            else
            {
                v.push_back(fc);
            }

            e *= 10;
            if (e % d == 0)
            {
                v.clear();
                break;
            }

            e = e % d;
        }

        if (l < v.size())
        {
            l = v.size();
            ans = d;
        }
    }

    cout << ans << endl;

    return 0;
}