Problem 20


1000の階乗で各桁を和を求めろという問題。10になる組み合わせを省いて
いったら大した数にならないのかな〜って考えたんだけど、全然そんなこと
ありませんでした。なので定番の配列を使って多倍長整数演算を行う手法で
解決しました。これだとせいぜい数百要素使えば解くことができるので楽です。
時間もそこまでかからないですし。

#!/usr/bin/perl
use strict;
use warnings;

print "Answer is ", p20(1000), "\n"; # Answer is 648

sub p20 {
    my ($limit) = @_;

    my @array1 = reverse split //, $limit;
    my @range  = reverse (2..($limit-1));

    for my $i (@range) {
        my @array2 = reverse split //, $i;

        @array1 = multi_operation(\@array1, \@array2);
    }

    my $answer = 0;
    map {$answer += $_} @array1;

    return $answer;
}

sub multi_operation {
    my ($array_ref1, $array_ref2) = @_;

    my @answer;
    my $length1 = (scalar @{$array_ref1}) - 1;
    my $length2 = (scalar @{$array_ref2}) - 1;

    for my $j (0..$length1) {
        for my $i (0..$length2) {
            my $mul = $array_ref1->[$j] * $array_ref2->[$i];
            my $div = 0;
            my $mod = $mul;

            if ($mul >= 10) {
                $div = int($mul / 10);
                $mod = $mul % 10;
                $answer[$i + $j + 1] += $div;
            }

            $answer[$i + $j]     += $mod;

            if ($answer[$i + $j] >= 10) {
                $answer[$i + $j + 1] += int($answer[$i + $j] / 10);
                $answer[$i + $j]     = $answer[$i + $j]  % 10;
            }
        }
    }

    return @answer;
}