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

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

13で割り切れるための判定条件

ある数値が13で割り切れるかどうかは、以下のいずれかの性質を使って確認できます。

方法1：3桁ブロックの交互和を利用する

数値を右から左へ向かって3桁ずつのブロックに分割し、それらを交互に加算・減算します（交互和）。この結果が13で割り切れる場合、元の数値も13で割り切れます。

例として「2911285」を見てみましょう。3桁ごとのブロックに分けると「2」「911」「285」となり、交互和は 2 − 911 + 285 = -650 となります。-650 は13で割り切れるため、2911285 も13で割り切れることがわかります。

方法2：最下位の桁に4倍を加算する

最下位の1桁を取り除いた残りの数に、取り除いた桁の4倍を加えます。この操作を繰り返し、得られた数値が13で割り切れれば、元の数値も13で割り切れます。

例として「2353」を考えます。

• 1回目：235 + 3 × 4 = 247
• 2回目：24 + 7 × 4 = 52

52 は13で割り切れるため、元の数値 2353 も13で割り切れることが確認できました。

C++による実装例

以下のコードは、方法1（3桁ブロックの交互和）を用いて、文字列として与えられた巨大な数値が13で割り切れるかどうかを判定するプログラムです。

#include <bits/stdc++.h>
using namespace std;
bool isDiv13(string num){
    int length = num.size();
    if (length == 1 && num[0] == '0')
        return true;
    if (length % 3 == 1) { // 桁数が3で割り切れない場合（余り1）
        num += "00";
        length += 2;
    } else if (length % 3 == 2){ // 桁数が3で割り切れない場合（余り2）
        num += "0";
        length += 1;
    }
    int sum = 0, p = 1;
    for (int i = length - 1; i >= 0; i--) {
        int set = 0;
        set += (num[i--] - '0');
        set += (num[i--] - '0') * 10;
        set += (num[i] - '0') * 100;
        sum = sum + set * p;
        p *= (-1);
    }
    sum = abs(sum);
    return (sum % 13 == 0);
}
int main() {
    string num = "83959092724";
    if(isDiv13(num)){
        cout << "Divisible";
    } else {
        cout << "Not Divisible";
    }
}

出力結果

Divisible

コードのポイント

• 桁数が3の倍数でない場合は、末尾に「0」を補って3桁ずつに区切れるようにしています。
• 右端から3桁ずつ取り出して1つの数値にまとめ、符号（+1 / -1）を交互に掛けながら合計しています。
• 最終的な合計の絶対値が13で割り切れるかどうかを判定することで、元の巨大な数値の割り切り判定が可能になります。

この手法を使えば、long long 型などの標準的な整数型の範囲を超えるような巨大な数値でも、文字列として処理することで効率的に13での割り切り判定を行えます。