C++で巨大な数Nの「N % 4（4で割った余り）」を効率的に求める方法

この問題では、非常に大きな整数を表す文字列 num が与えられます。求めるのは、桁数が大きい値 N に対して「N % 4（4で割った余り）」を計算することです。

問題の概要

与えられた巨大な数値を 4 で割った余り（剰余）を求めるのが課題です。

入力例

num = 453425245

出力例

1

解法のアプローチ

この問題には、解決の鍵となる便利な性質があります。それは「ある数を 4 で割った余りは、その数の下2桁だけで決まる」というものです。

これは、100 が 4 の倍数であるため、どれほど桁数が多くても下2桁より上の部分は必ず 4 の倍数になるからです。つまり、たとえ何万桁の巨大な数であっても、下2桁を取り出して 4 で割るだけで答えが求まります。

解法の手順：

• 桁数が1桁の場合：その数字をそのまま 4 で割った余りを返します。
• 桁数が2桁以上の場合：下2桁からなる整数を作成し、それを 4 で割った余りを返します。

この解法の動作を示すプログラム：

C++実装例

#include <bits/stdc++.h>
using namespace std;
int calc4Mod(string num, int len) {
    int rem;
    if (len == 1)
        rem = num[0] - '0';
    else
        rem = (num[len - 2] - '0') * 10 + num[len - 1] - '0';
        return (rem % 4);
}
int main() {
    string num = "84525765476513";
    int len = num.length();
    cout<<"この数を 4 で割った余りは "<<calc4Mod(num, len);
    return 0;
}

実行結果

この数を 4 で割った余りは 1

まとめ

巨大な数 N を 4 で割った余りを求める場合でも、数全体を処理する必要はありません。「100 が 4 の倍数である」という性質を利用すれば、下2桁だけを確認するだけで定数時間 O(1) で答えを導けます。文字列として渡される巨大な数でも、この方法ならオーバーフローの心配なく安全かつ効率的に計算できるのが大きな利点です。