不重复的幂

作者：Flavio Poletti

考虑 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-polettix.pl

use v6;

# Range upper limit, defaults to challenge's value
my $max = @*ARGS.shift || 100;

# Integers up to the square root of the maximum value may lead to
# colliding items in the whole list, so we have to count them
# properly in order to get rid of duplicates. For example,
#
#    2**8=256 is equal to 16**2
#
# In addition to this, some items under the square root might
# lead to another kind of duplication. For example,
#
#    2**4=16  is equal to  4**2
#
# Hence, we'll skip the latter completely in our analysis from 2
# to the square root, and count the former according to the possible
# exponents.
my (%mark_for, %already_done);
for 2 .. sqrt($max).Int -> $i {
    next if %already_done{$i};

    my $x = $i;
    my $exp = 1;
    while ($x <= $max) {
        %already_done{$x} = 1;
        for 2 .. $max -> $f {
            %mark_for{$i} ||= {}; # avoid autovivification for now...
            %mark_for{$i}{$f * $exp} = 1;
        }
        ++$exp;
        $x *= $i;
    }
}

# Now, every element not already considered contributes only with
# unique elements. We have to remember that ranges start from 2, so
# we have to subtract 1 from $max
my $count = ($max - 1 - %already_done.keys) * ($max - 1);

# Then, we add the unique elements from what we analysed before,
# simply counting the number of elements that could potentially collide
for %mark_for.values -> $v {
    $count += $v.elems;
}

$count.say;