【プログラミング】計算量を再認識した話【PHP】

プログラミング

2019.06.24

この記事は約6分で読めます。

答えは 7の倍数の「7, 14, 21, 28, 35, 42, 49」以外の数なので 43個です！

程よい難易度の問題を出されると答えが気になってしまい、クリックしたくなるのが人間の習性だそうです！
アイキャッチで釣られた人すみません…笑

今回はそれに関連したプログラミングの話になります。

先日こちらの問題を解こうとしたところ勉強になったので紹介します。

AtCoder Beginner Contest 131 C – Anti-Division

問題文

整数 A, B, C, D が与えられます。
A 以上 B 以下の整数のうち、C でも D でも割り切れないものの個数を求めてください。

問題文

誤った解法
正しい解法
ちょっと詳しい話
まとめ

誤った解法

日本語の通り、プログラムを書いてみます

<?php
    const INPUT_DELIMITER = " ";

    // 入力
    $input = fgets(STDIN);
    $inputArray = explode(INPUT_DELIMITER, $input);

    $A = $inputArray[0];
    $B = $inputArray[1];
    $C = $inputArray[2];
    $D = $inputArray[3];

    // 割り切れないものの個数
    $count = 0;

    // A 以上 B 以下の整数
    for ($i = $A; $i <= $B; $i++) {
        // C でも割り切れない かつ D でも割り切れない
        if ($i % $C != 0 && $i % $D != 0) {
            // その個数を数える
            $count++;
        }
    }

    echo $count;

数が少なければ問題なく動きます。

しかし大きな数になるとこのプログラムは重すぎて動かなくなってしまいます。

入力例3より 
    ~省略~
    $A = $inputArray[0]; // 314159265358979323
    $B = $inputArray[1]; // 846264338327950288
    $C = $inputArray[2]; // 419716939
    $D = $inputArray[3]; // 937510582

    $count = 0;
    for ($i = $A; $i <= $B; $i++) {
        // 50京(!?)回計算してしまう！！
        if ($i % $C != 0 && $i % $D != 0) {
            // その個数を数える
            $count++;
        }
    }

正しい解法

そのため別の方法で計算していきます

C でも割り切れない かつ D でも割り切れない

はド・モルガンの法則より、言い換えると、

C で割り切れる または D でも割り切れる

そのような数を出せばOKです。

上のベン図のように、CとDの公倍数は共通部分のため、

Cの倍数の総数 + Dの倍数の総数 – CとDの公倍数

を求めていきます。（高校でやったな…）
最小公倍数の求め方に関してはEuclidの互除法を用いました。
もはや忘れ去られた知識なのでググりました…

<?php
    const INPUT_DELIMITER = " ";

    // 最小公倍数を求める
    function getLCM ($a, $b) {
        return $a * $b / getGCM($a, $b);
    }

    // 最大公約数を求める
    function getGCM ($a, $b) {
        if ($a < $b) {
            list($min, $max) = [$a, $b];
        } else {
            list($min, $max) = [$b, $a];
        }

        $mod = $max % $min;
        if ($mod === 0) {
            return $min;
        }
        // 数を変えてもう一度計算する
        return getGCM($min, $mod);
    }

    // 入力
    $input = fgets(STDIN);
    $inputArray = explode(INPUT_DELIMITER, $input);

    $A = $inputArray[0];
    $B = $inputArray[1];
    $C = $inputArray[2];
    $D = $inputArray[3];


    // CとDの公倍数
    $CD = getLCM($C, $D);

    $range = $B - $A;
    // 割り切れないものの個数
    $countC = floor($range / $C);
    $countD = floor($range / $D);
    $countCD = floor($range / $CD);

    // 計算
    $count = bcsub($range , ($countC + $countD - $countCD));
    echo $count;

最大公約数を計算する上で数回計算が入りますが、最初の解法とは異なり膨大な計算をする必要はありません。