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

本記事では、C++を用いて、ある数が11で割り切れるかどうかを判定する方法を解説します。ここで扱うのは非常に大きな数であるため、int 型や long long 型といった標準的な整数型には収まりません。そこで、数値を文字列として受け取り、桁ごとに処理を行います。

11の倍数判定法とは

ある整数が11で割り切れるかどうかは、次の有名な判定法で簡単に確認できます。

• 左から順に各桁を見て、奇数番目の桁の合計と偶数番目の桁の合計をそれぞれ求める。
• 両者の差が0、または11の倍数であれば、その数は11で割り切れる。

特に、奇数番目の桁の合計と偶数番目の桁の合計が一致していれば、差は必ず0になるため、その数は確実に11で割り切れます。

C++での実装例

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

bool isDiv11(string num){
    int n = num.length();
    long odd_sum = 0, even_sum = 0;
    // 各桁を走査し、位置ごとに合計を求める
    for(int i = 0; i < n; i++){
        if(i % 2 == 0){
            odd_sum += num[i] - '0';
        } else {
            even_sum += num[i] - '0';
        }
    }
    // 差が11の倍数（0を含む）なら割り切れる
    return abs(odd_sum - even_sum) % 11 == 0;
}

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

出力結果

Divisible

コードの解説

num[i] - '0' の部分では、文字として格納された数字を対応する整数値に変換しています。ループ内では、添字 i が偶数の桁を odd_sum に、奇数の桁を even_sum に加算していきます。最後に両者の差を計算し、その差が11の倍数であれば true を返します。

このアルゴリズムの計算量は、桁数を n とすると O(n)、必要な追加メモリは O(1) です。したがって、どれほど桁数が多い数でも、文字列として読み込めば線形時間で効率的に判定できます。