Project Euler 26

単位分数とは分子が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... 
という数字であり、6が循環節であることを表している。1/7 循環節は6桁ある。

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

A = 
   Table[
      Length[ RealDigits[1/i][[1, 1]] ]
   , {i, 1000}
   ];
Position[A, Max[A]]

IntegerDigitsと同じように、RealDigitsは整数の桁のリストと小数点の位置を返します。
例えば RealDigits[12.345] の場合、 {{1, 2, 3, 4, 5}, 2}
となります。

ここまではIntegerDigitsとなんらかわりない機能のように思えますが、RealDigitsは、例えばある循環小数、

RealDigits[1/7]

を実行すると

{{1, 4, 2, 8, 5, 7}}, 0}

のように、循環する部分のみを返してくるというチートのような機能を有しています。
この桁数を数えて全部足せばいいわけです。楽！

C/C++

#include <iostream>
using namespace std;

// n/d の循環小数を求め、循環節の長さを返す。
// aの大きさはd以上である必要があります
int repDecimal(int n, int d){
	int a[1000], q, r;

	for(int i=0 ; i<1000 ; i++){
		a[i] = 0;
	}
	q = n/d;
    r = n - q*d;
	//cout << n << " / " << d << " = " << q << ".";

	int i=0;
    // 余りがゼロになるまで繰り返す
	while(r != 0){
        n = r * 10;
        q = n/d;
        r = n - q*d;
        if (a[r] == 1){
            // 循環したとき
            //cout << "...";
            break;
        }
		i++;
        a[r]++;
        //cout << q;
    }
    //cout << endl;
	return i;
}

int main(void)
{
    int k, length=0, ans;

	for(int i=1 ; i<1000 ; i++){
	    k = repDecimal(1,i);
		if( length < k){
			length = k;
			ans = i;
		}
	}	
	cout << ans << endl;

	int end;
	cin >> end;
}

同じ余りが出てきたら循環している、という発想がでてからはすぐでした。