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

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

75で割り切れるための条件

75 = 3 × 25 であり、3と25は互いに素です。したがって、次の性質が成り立ちます。

ある数が75で割り切れる ⇔ その数が3と25の両方で割り切れる

3で割り切れる条件

各桁の数字の合計が3で割り切れる場合、その数は3で割り切れます。

25で割り切れる条件

下2桁の値が25で割り切れる（つまり「00」「25」「50」「75」のいずれかで終わる）場合、その数は25で割り切れます。

アルゴリズムの手順

1. 数値を文字列として受け取ります。
2. 全桁の数字の合計を計算し、3で割り切れない場合は false を返します。
3. 下2桁を整数値に変換し、25で割り切れる場合は true、そうでなければ false を返します。

C++による実装例

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

bool isDiv75(string num){
    int n = num.length();
    // 各桁の合計を計算（ASCII値の合計から '0' × 桁数 を引く）
    long sum = accumulate(begin(num), end(num), 0) - '0' * n;
    if(sum % 3 != 0)
        return false;
    // 下2桁を整数として取得
    int last_two_digit_val = (num[n-2] - '0') * 10 + ((num[n-1] - '0'));
    if(last_two_digit_val % 25 == 0)
        return true;
    return false;
}

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

実行結果

Divisible

処理のポイント

• accumulate(begin(num), end(num), 0) は文字列内の各文字のASCIIコード値の合計を求めます。そこから '0' × 桁数 を引くことで、実際の数字の合計が計算できます。
• 下2桁は (num[n-2] - '0') * 10 + (num[n-1] - '0') の式で整数化し、25の剰余を確認します。
• この手法なら整数型の上限に縛られず、任意の桁数の巨大な数値にも対応できます。

例として挙げた数値「1754586672150」の場合、各桁の合計は57となり3で割り切れ、下2桁は「50」で25でも割り切れるため、出力は「Divisible」となります。