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

はじめに

本記事では、ある数値が3で割り切れるかどうかを判定する方法を解説します。ここで扱うのは非常に大きな数値であるため、通常の整数型(int や long long)では表現できません。そこで、数値を文字列として受け取り、判定処理を行います。

3の倍数判定の原理

3の倍数判定には、よく知られた数学的性質を利用します。

「各桁の数字の合計が3で割り切れるならば、その数も3で割り切れる」

例えば、123 という数値の場合、1 + 2 + 3 = 6 となり、6 は3で割り切れるため、123 も3で割り切れることが分かります。この性質は桁数が何桁であっても成り立つため、文字列として表現された巨大な数値にも適用できます。

アルゴリズムの流れ

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

C++による実装例

#include <bits/stdc++.h>
using namespace std;
bool isDiv3(string num){
    int n = num.length();
    long sum = accumulate(begin(num), end(num), 0) - '0' * n;
    if(sum % 3 == 0)
       return true;
    return false;
}
int main() {
    string num = "3635883959606670431112222";
    if(isDiv3(num)){
       cout << "Divisible";
    } else {
       cout << "Not Divisible";
    }
}

出力結果

Divisible

コードの解説

このコードのポイントは、accumulate 関数を使って文字列内の全文字(各桁)を合計している部分です。

文字のASCIIコードをそのまま合計すると、実際の数値より '0'(ASCIIコード48)の分だけ大きくなるため、'0' * n(桁数 × 48)を差し引くことで、各桁の数字そのものの合計を求めています。

その後、合計値を3で割った余りが0であれば、その巨大な数値は3で割り切れると判定できます。

計算量について

このアルゴリズムの時間計算量は O(n)(n は文字列の長さ=桁数)です。数値全体を一度走査するだけなので、桁数が数千、数万桁であっても高速に判定できます。

まとめ

巨大な数値の3の倍数判定は、数値を文字列として扱い、「各桁の合計が3で割り切れるか」を確認することで簡単に実現できます。標準ライブラリの accumulate を活用すれば、簡潔で読みやすいコードになります。同様の手法は9の倍数判定にも応用できるため、ぜひ覚えておきましょう。