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

この記事では、非常に大きな数値が20で割り切れるかどうかを判定する方法を解説します。数値が int 型や long long 型の範囲を超えるほど大きい場合、通常の数値型では扱えないため、文字列として受け取る必要があります。

判定の考え方

ある数が20で割り切れるためには、「その数が10で割り切れ、かつ10で割った商が2で割り切れる」という条件を満たす必要があります。これをもっとシンプルに考えると、次の2つの条件に整理できます。

• 条件1: 最後の桁(1の位)が「0」であれば、その数は10で割り切れる
• 条件2: 下から2番目の桁(10の位)が偶数であれば、10で割った商も2で割り切れる

つまり、末尾が「0」であり、かつ十の位が偶数であることが確認できれば、その数は20で割り切れると判定できます。実際に桁を2つ確認するだけなので、計算量はO(1)と非常に効率的です。

具体例

例として「54871584540」という数値を見てみましょう。

• 最後の桁は「0」→ 10で割り切れる ✓
• 下から2番目の桁は「4」→ 偶数なので条件を満たす ✓

両方の条件を満たしているため、54871584540は20で割り切れる数です。

C++での実装例

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

bool isDiv20(string num){
    int n = num.length();
    // 最後の桁が0でなければ10で割り切れない
    if(num[n - 1] != '0')
        return false;
    // 下から2番目の桁を数値に変換
    int second_last = num[n - 2] - '0';
    // 十の位が偶数なら20で割り切れる
    if(second_last % 2 == 0)
        return true;
    return false;
}

int main() {
    string num = "54871584540";
    if(isDiv20(num)){
        cout << "Divisible";      // 割り切れる
    }else{
        cout << "Not Divisible";  // 割り切れない
    }
}

出力結果

Divisible

コードのポイント

• 文字列の各桁は char 型として格納されているため、'0' を引くことで整数値に変換しています。
• 文字列の長さから末尾のインデックス n - 1 と n - 2 を参照することで、どれほど大きな数でも即座に判定できます。
• 先頭に不要な空白や符号が含まれる可能性がある場合は、事前に正規化しておくとより堅牢になります。

このように、巨大な数値の割り切り判定では、数全体を演算するのではなく「桁の性質」を利用することが重要です。20以外の数についても同様の手法(例えば4なら下2桁、8なら下3桁をチェックなど)で応用できます。