C++で文字列形式の巨大な数値が12で割り切れるかを判定する方法

このチュートリアルでは、文字列形式で与えられた非常に大きな数値が12で割り切れるかどうかを判定するプログラムをC++で作成します。

大きな数値は標準の整数型に収まらない場合があるため、数値を直接除算するのではなく、数学的な性質を利用して判定します。ここで鍵となるのは次の事実です。ある数が3と4の両方で割り切れるならば、その数は12でも割り切れるというものです。

12の倍数の判定条件

3で割り切れる条件

各桁の数字の合計が3で割り切れる場合、その数は3で割り切れます。

4で割り切れる条件

下2桁の数値が4で割り切れる場合、その数は4で割り切れます。

これらの性質を組み合わせることで、巨大な数値でも効率よく12との整除性を判定できます。それでは、実際のコードを見ていきましょう。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
bool isNumberDivisibleBy12(string num) {
    if (num.length() >= 3) {
        int last_digit = (int)num[num.length() - 1];
        if (last_digit % 2 != 0) {
            return 0;
        }
        int second_last_digit = (int)num[num.length() - 2];
        int sum = 0;
        for (int i = 0; i < num.length(); i++) {
            sum += num[i];
        }
        return (sum % 3 == 0 && (second_last_digit * 10 + last_digit) % 4 == 0);
    }
    else {
        int number_as_int = stoi(num);
        return number_as_int % 12 == 0;
    }
}
int main() {
    string num = "1212121212121212121212121212";
    if (isNumberDivisibleBy12(num)) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

Yes

コードの解説

プログラムの流れは以下のとおりです。

まず、桁数が3以上の場合を考えます。最初のチェックとして、最下位の桁（一の位）が奇数であれば、その数は偶数ではないため4で割り切れず、結果的に12でも割り切れないことが確定します。この時点で即座に false を返すことで、無駄な計算を省いています。

次に、各桁の文字コード値を合計しています。ASCIIコードでは「'0'」が48（3の倍数）であるため、各桁の文字コード値の合計を3で割った余りは、各桁の数字そのものの合計を3で割った余りと一致します。これにより、文字列のままでも3との整除性を正しく判定できます。

同様に、下2桁についても文字コード値を使って計算しています。「'0'」の文字コード48は4の倍数なので、(十の位の文字コード × 10 + 一の位の文字コード) を4で割った余りは、実際の下2桁の数値を4で割った余りと等しくなります。

一方、桁数が2以下の場合は数値が小さいため、stoi() で整数に変換して直接12で割った余りを確認すれば十分です。

まとめ

このように、3と4の整除性を組み合わせることで、文字列形式の巨大な数値でも12で割り切れるかどうかを簡単に判定できます。この手法は、標準の整数型では扱えないような数百桁の数値に対しても有効です。チュートリアルについてご不明な点があれば、コメント欄でお気軽にお尋ねください。