/* http://projecteuler.net/
 *
 * Problem 26
 *
 * Find the value d<1000 for which 1/d contains the longest
 * recurring cycle in its decimal fraction part.
 *
 * Solution by Melkor (Filip Niksic, fniksic@gmail.com)
 *
 **/

#include <iostream>
#include <bitset>

using namespace std;

/* Notice that the length of a recurring cycle cannot be larger
 * than d. So it makes sense to start from 999 downto 1 and stop
 * the search once we drop below the maximum cycle length found.
 **/
int main() {
    bitset<1000> rem;
    int appearance[1000];
    int maxd, maxCycle = 0;

    for (int d = 999; d > maxCycle; --d) {
	rem.reset();
	int i = 1, l = 0;
	for ( ; !rem.test(i); ++l, i=(i*10)%d) {
	    rem.set(i);
	    appearance[i] = l;
	}
	if (l - appearance[i] > maxCycle) {
	    maxd = d;
	    maxCycle = l - appearance[i];
	}
    }

    cout << "d = " << maxd << " (cycle length = " << maxCycle << ")\n";

    return 0;
}