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

本記事では、ある数値が25で割り切れるかどうかを判定する方法を解説します。扱う数値が非常に大きい（桁数が多い）場合、通常の整数型では表現しきれないため、数値を文字列として受け取って処理します。

25の倍数の判定ルール

数値が25で割り切れるかどうかは、下2桁だけを見れば判定できます。具体的には、以下のいずれかの条件を満たしていれば、その数は25で割り切れます。

• 下2桁が「00」である
• 下2桁の数値自体が25で割り切れる（00、25、50、75）

これは、100が25で割り切れるため、下2桁より上の部分は必ず25の倍数になるという性質によるものです。

サンプルコード

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

bool isDiv25(string num){
    int n = num.length();
    // 下2桁を数値として取り出す
    int last_two_digit_val = (num[n-2] - '0') * 10 + ((num[n-1] - '0'));
    // 下2桁が25で割り切れるか判定
    if(last_two_digit_val % 25 == 0)
        return true;
    return false;
}

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

実行結果

Divisible

コードの解説

このプログラムのポイントは以下の通りです。

1. 文字列の長さ n を取得し、末尾から2番目と1番目の文字にアクセスします。
2. 各文字から '0' を引くことで、文字を対応する整数値に変換します。
3. 十の位を10倍して一の位と足し合わせることで、下2桁の整数値を求めます。
4. その値を25で割った余りが0であれば、元の数値は25で割り切れると判定できます。

この手法を使えば、どれほど桁数が大きい数値でも、文字列として読み込むだけで効率的に25の倍数かどうかを判定できます。計算量はO(1)であり、非常に高速です。