循环节

作者：Shlomi Fish

https://projecteuler.net/problem=26

单位分数是指分子为 1 的分数。分母为 2 到 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...，其循环节长度为 1。可以看出，1/7 的循环节长度为 6。

求出 d < 1000 时，1/d 的小数部分循环节长度最长的 d 值。

源代码：prob026-shlomif.pl

use v6;

sub find_cycle_len(Int $n) returns Int {
    my %states;

    my $r = 1;
    my $count = 0;

    while ! ( %states{$r}:exists ) {
        # $*ERR.say( "Trace: N = $n ; R = $r" );
        %states{$r} = $count++;
        ($r *= 10) %= $n;
    }

    return $count - %states{$r};
}

my $max_cycle_len = -1;
my $max_n;

for (2 .. 999) -> $n {
    if ((my $cycle_len = find_cycle_len($n)) > $max_cycle_len) {
        $max_n = $n;
        $max_cycle_len = $cycle_len;
    }
}

say "The recurring cycle is $max_n, and the cycle length is $max_cycle_len";