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

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

15の倍数判定の考え方

数値が15で割り切れるためには、「5で割り切れる」かつ「3で割り切れる」という2つの条件を満たす必要があります。これは、15 = 5 × 3 であり、5と3が互いに素であるためです。

• 5で割り切れる条件： 最後の桁（1の位）が「0」または「5」であること
• 3で割り切れる条件： 各桁の数字の合計が3で割り切れること

C++での実装例

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

コードの解説

isDiv15関数は、以下の手順で判定を行っています。

1. まず、文字列の最後の文字が「5」または「0」であるかを確認し、該当しなければ即座にfalseを返します（5の倍数判定）。
2. 次に、accumulate関数で各桁の文字コードの合計を計算し、そこから '0' × 桁数 を引くことで、実際の各桁の数字の合計値を求めます。
3. 合計が3で割り切れればtrue、そうでなければfalseを返します。

実行結果

Divisible

このように、巨大な数値でも文字列として処理すれば、整数型のオーバーフローを気にすることなく、15の倍数かどうかを簡単に判定できます。同様の手法は、他の合成数の倍数判定にも応用可能です。