C/C++でモジュラー方程式（剰余等式）の解の個数を求めるプログラム

本記事では、モジュラー方程式（剰余等式）に関する興味深い問題を取り上げます。2つの値 A と B が与えられたとき、「(A mod X) = B」を満たす変数 X の候補がいくつあるかを求めるというものです。

例として、A = 26、B = 2 の場合を考えてみましょう。この条件を満たす X の値は {3, 4, 6, 8, 12, 24} の6つとなるため、答えは 6 になります。それでは、処理の流れを理解するためにアルゴリズムを見ていきましょう。

アルゴリズム

possibleWayCount(a, b)

begin
    if a = b, then there are infinite solutions
    if a < b, then there are no solutions
    otherwise div_count := find_div(a, b)
    return div_count
end

find_div(a, b)

begin
    n := a – b
    div_count := 0
    for i in range 1 to square root of n, do
        if n mode i is 0, then
            if i > b, then
                increase div_count by 1
            end if
            if n / i is not same as i and (n / i) > b, then
                increase div_count by 1
            end if
        end if
    done
end

ポイントは、(A mod X) = B が成り立つとき、X は必ず「A − B」の約数であり、かつ B より大きい値でなければならないという性質です。したがって、A − B の約数を効率よく列挙し、B より大きいものだけをカウントすれば答えが求まります。約数の探索は √n まで調べれば十分なので、計算量は O(√n) に抑えられます。

実装例（C++）

#include <iostream>
#include <cmath>
using namespace std;
int findDivisors(int A, int B) {
    int N = (A - B);
    int div_count = 0;
    for (int i = 1; i <= sqrt(N); i++) {
        if ((N % i) == 0) {
            if (i > B)
                div_count++;
            if ((N / i) != i && (N / i) > B) //重複して数えないようにする
                div_count++;
        }
    }
    return div_count;
}
int possibleWayCount(int A, int B) {
    if (A == B) //一致する場合は解が無限に存在する
        return -1;
    if (A < B) //A < B の場合は解なし
        return 0;
    int div_count = 0;
    div_count = findDivisors(A, B);
    return div_count;
}
void possibleWay(int A, int B) {
    int sol = possibleWayCount(A, B);
    if (sol == -1)
        cout << "For A: " << A << " and B: " << B << ", X can take infinite values greater than " << A;
    else
        cout << "For A: " << A << " and B: " << B << ", X can take " << sol << " values";
}
int main() {
    int A = 26, B = 2;
    possibleWay(A, B);
}

出力結果

For A: 26 and B: 2, X can take 6 values

このプログラムでは、A と B が等しい場合（-1 を返して「無限の解」があることを示す）、A が B より小さい場合（解なしとして 0 を返す）といったエッジケースも適切に処理しています。また、√N までループすることで、約数ペア (i, N/i) の両方を同時にチェックし、同じ約数を二重にカウントしないよう配慮されています。これにより、大きな値に対しても高速に解の個数を求めることができます。