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; }