不重复的幂

作者：Gerhard R

https://projecteuler.net/problem/29

考虑 a^b 的所有整数组合，其中 2 ≤ a ≤ 5 且 2 ≤ b ≤ 5

2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125

如果将它们按数字顺序排列，并删除任何重复项，我们将得到以下 15 个不同项的序列

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

对于 2 ≤ a ≤ 100 且 2 ≤ b ≤ 100，a^b 生成的序列中有多少个不同的项？

源代码： prob029-gerdr.pl

use v6;

# compute number of unique powers a**b with bases \a in range 2..A
# and exponents \b in range 2..B

sub count-naively(Int $A, Int $B) {
    +(2..$A X=> 2..$B).classify({ .key ** .value })
}

sub count-smartly(Int $A, Int $B) {
    my (%powers, %count);

    # find bases which are powers of a preceding root base
    # store decomposition into base and exponent relative to root
    for 2..Int(sqrt $A) -> $a {
        next if $a ~~ %powers;
        %powers{$a, $a**2, $a**3 ...^ * > $A} = $a X=> 1..*;
    }

    # count duplicates
    for %powers.values -> $p {
        for 2..$B -> $e {
            # raise to power \e
            # classify by root and relative exponent
            ++%count{$p.key => $p.value * $e}
        }
    }

    # add +%count as one of the duplicates needs to be kept
    return ($A - 1) * ($B - 1) + %count - [+] %count.values;
}

sub cross(@a, @b) { @a X @b }
sub dups(@a) { @a - @a.uniq }
sub count-feedly(Int $A, Int $B) {
    2..Int(sqrt $A) \
    ==> map -> $a { ($a, $a**2, $a**3 ...^ * > $A) Z=> ($a X 1..*).tree } \
    ==> reverse() \
    ==> hash() \
    ==> values() \
    ==> cross(2..$B) \
    ==> map -> $n, [$r, $e] { ($r) => $e * $n } \
    ==> dups() \
    ==> (($A - 1) * ($B - 1) - *)();
}

sub bench(|) {
    my $start = now;
    my $result = callsame;
    my $end = now;
    return $result, round ($end - $start) * 1000;
}

multi MAIN(Int $N, Bool :$verify, Bool :$feeds) {
    nextwith($N, $N, :$verify, :$feeds)
}

multi MAIN(Int $A = 100, Int $B = 100, Bool :$verify, Bool :$feeds) {
    &count-naively.wrap(&bench);
    &count-smartly.wrap(&bench);
    &count-feedly.wrap(&bench);

    my ($result, $runtime) = ($feeds ?? &count-feedly !! &count-smartly)($A, $B);
    say $result;

    printf "expected %u [%ums]\n", count-naively $A, $B if $verify;
}