読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Project Euler - Problem 26

Problem 26

d < 1000のとき, 1/dの中で循環節が最も長くなるようなdを求める問題.

use strict;
use warnings;

use Math::BigInt;

for (reverse 1..1000) {
    my $n = Math::BigInt->new('1'.'0'x(2*$_))->bdiv($_)->bstr;

    if ($n =~ /(\d{2,}?)\1/ && length $1 == $_ - 1) {
        print "$_\n";
        last;
    }
}

1/dにおける循環節の長さは, 最長でd-1らしいので, この条件を使って調べてみました.
数字の大きい方から調べて, 除数がnのとき, 順関節の長さがn-1ならば最長, ということで探索を打ち切っています.