C++で巨大な数値が9で割り切れるかどうかを判定する方法

本記事では、ある数値が9で割り切れるかどうかを判定する方法を解説します。対象となる数値は非常に大きいため、通常の整数型では扱いきれず、文字列として受け取る必要があります。

9の倍数の判定ルール

数学でよく知られた性質として、「各桁の数字の合計が9で割り切れるならば、その数自身も9で割り切れる」というものがあります。この性質を利用すれば、どれほど巨大な数値でも、文字列として各桁を処理するだけで簡単に判定できます。

アルゴリズムの手順

1. 数値を文字列として受け取る
2. 各桁の数字をすべて合計する
3. 合計が9で割り切れれば「割り切れる」、そうでなければ「割り切れない」と判定する

C++による実装例

#include <bits/stdc++.h>
using namespace std;

bool isDiv9(string num){
    int n = num.length();
    long sum = accumulate(begin(num), end(num), 0) - '0' * n;
    if(sum % 9 == 0)
        return true;
    return false;
}

int main() {
    string num = "630720";
    if(isDiv9(num)){
        cout << "Divisible";
    } else {
        cout << "Not Divisible";
    }
}

出力結果

Divisible

コードの解説

このコードでは、STLのaccumulate関数を使って、文字列内の全文字のASCIIコード値の合計を計算しています。各文字には文字「'0'」分のコード値が余分に含まれているため、文字数 n に「'0'」の値を掛けた分を差し引くことで、実際の各桁の数字の合計を求めています。

例として「630720」を挙げると、各桁の合計は 6 + 3 + 0 + 7 + 2 + 0 = 18 となり、18は9で割り切れるため、元の数値も9で割り切れると判定されます。この手法なら、long long型や多倍長演算ライブラリを使わなくても、任意の桁数の数値を効率的にチェックできます。