友愛数 (EPOCH@まつやま - 本選 1)

AWK Users JP :: EPOCH@まつやまの例題を解いてみるではEPOCH@まつやまの問題例を解きましたが、今回は本選第 1 ステージの問題 (PDF) を解いていきます。

問題としては問題例の複数の組み合わせをきちんと把握していれば解ける問題ですが、さすがに問題例のように 1 ページで 10 問を掲載するのは厳しいため、1 問づつ掲載します。 ただし、全ての問題を解くかどうかは今のところ決めていません。

友愛数の問題ですが、政治の話とは全く関係なく、友愛数 - Wikipedia に掲載されているような数です。

既に AWK Users JP :: EPOCH@まつやまの例題を解いてみるでも使った方式で約数を求めることができます。

#! /usr/local/bin/gawk -f
# epoch_problem_H1.awk
# 友愛数
# usage: gawk -f epoch_problem_H1.awk file

NR == 1 {
    num = $0;
}

NR != 1 {
    sum_div1 = 0;
    sum_div2 = 0;
    num1 = $1;
    num2 = $2;

    for (i = 1; i < num1; i++) {
        if (num1 % i == 0) {
            sum_div1 += i;
        }
    }

    for (i = 1; i < num2; i++) {
        if (num2 % i == 0) {
            sum_div2 += i;
        }
    }

    if (sum_div1 == num2 && sum_div2 == num1) {
        count++;
    }
}

END {
    print count;
}

基本的に難しい問題ではありませんが、計算速度を要求される場合にはもう少し工夫が必要です。

実際に解いてみます。

$ cat epoch_problem_H1.txt
5
1510 6063
220 284
2643 7144
1836 2106
118 293

$ gawk -f epoch_problem_H1.awk epoch_problem_H1.txt
1

実際の本選でこのレベルの問題をどのくらいで解ければよいのか不明ですが、短時間で解く必要があるのであれば、問題の解き方を決めたら迷わずに解くのが良さそうです。