Problem 26 がやっと解けた

循環小数についての種々の考察 を参考にしてやっと解けた。
Problem 26 を解く上で重要なポイントは

純循環小数 1/n の循環節の長さ r は 10^r ≡ 1 (mod n) を満たす最小の r である

ということ。
また、

既約分数 k/n が純循環小数である ⇔ n が 10 と互いに素

ということも知っている必要がある。どっちの証明も上記リンク先に書かれている。
俺はリンク先を読むまで下の事実は知らなかった。
あとは、最も長い循環節を持つ小数が純循環小数であることを信じてプログラムに解かせればいい。
10 の数百乗を計算する必要があるので、gmp を使った。

#include <stdio.h>
#include <gmp.h>

#define M 1000

int main(void)
{
  mpz_t p, r;
  mpz_init(p);
  mpz_init(r);
  unsigned maxlen = 0, imax = 0;
  unsigned i;
  for (i = 2; i < M; i++) {
    if (i % 2 == 0 || i % 5 == 0) {
      continue;
    }

    unsigned len = 1;
    mpz_set_ui(p, 10);
    while (mpz_mod_ui(r, p, i), mpz_cmp_ui(r, 1) != 0) {
      len++;
      mpz_mul_ui(p, p, 10);
    }
    if (len > maxlen) {
      maxlen = len;
      imax = i;
    }
  }
  printf("%u: %u\n", imax, maxlen);
  mpz_clear(p);
  mpz_clear(r);
  return 0;
}

この計算は一瞬で終わる