読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Project Euler - Problem 32

Problem 32

...今気づいたのですが, 日記の一覧を見ていると, オイラーの日記で投稿数を水増し(?)しているように見えます...よね.
Project Euler解答系以外の記事を日記の一覧から探すときにちょっと不便なので, 来月からは月初めの投稿を「5月のProject Euler」みたいな感じのタイトルにして, この記事に追記していく形で解答していこうと思います.

というわけで, Problem 32です.
問題を簡単に解説すると, 掛ける数・掛けられる数・積が1, 2, 3, 4, 5, 6, 7, 8, 9の組み合わせとなるような積の総数を求める問題です.

例えば, 39 * 186 = 7254で, 掛ける数・掛けられる数・積を組み合わせると3, 9, 1, 8, 6, 7, 2, 5, 4になります.
で, これをソートすると1, 2, 3, 4, 5, 6, 7, 8, 9.
1から9までの数字が, それぞれ1回ずつ出てきています. こういう掛ける数・掛けられる数・積の組み合わせを探す問題です.

n桁 * m桁の積は, 必ずn + m桁以下になります(例えば, 99 * 99 = 9801なので, 2桁 * 2桁 = 4桁. 10 * 10などの場合は, 10 * 10 = 100で2桁 * 2桁 = 3桁なので「以下」と表記した).
掛ける数の桁(n), 掛けられる数の桁(m), そして積の桁(n + m)の和は9でなければならないので, n + m + n + m = 9, つまりn + m = 4.5.
これより, 積は4桁の数値(1000〜9999)であるということがわかります.

これを踏まえて, 次のように実装してみました.

use strict;
use warnings;

my $result;

for my $product (1000..9999){
    for my $i (2..sqrt $product) {
        if ($product % $i == 0) {
            if ($product % $i == 0 && join('', sort split //, $product . $i . $product / $i) eq '123456789') {
                $result += $product;
                last;
            }
        }
    }
}

print "$result\n";

2つ目のfor文ですが, 掛ける数は2からsqrt(積)の範囲になります.
仮に掛ける数がこれ以上になってしまうと, 積をオーバーしてしまう為です.

で, if文以降ですが, ここは積を掛ける数で割った余りが0ならば, 掛けられる数が存在するので, 掛ける数・掛けられる数・積を文字列化し, splitしてからsortしてjoinで連結し, '123456789'と比較しています.
lastを挟んでいるのは, 積が同じで, 掛ける数と掛けられる数が入れ替わったパターンを回避する為です.