C++でモジュラ方程式（剰余方程式）の解の個数を求める方法

この記事では、モジュラ方程式（剰余方程式）の解とは何かを詳しく解説し、その解の個数を求めるプログラムをC++で作成します。まずは基本的な例から見ていきましょう。

Input : X = 30 Y = 2
Output : 4, 7, 14, 28
Explanation : 30 mod 4 = 2 (equals Y),
    30 mod 7 = 2 (equals Y),
    30 mod 14 = 2 (equals Y),
    30 mod 28 = 2 (equals Y)

上の例からわかるように、Xを割ったときの余りがYと等しくなる整数は、すべて解となります。この例では、30を4、7、14、28で割ると余りが2になり、これはYの値と一致しています。モジュラ方程式はこのようにして解くことができます。

解を求めるアプローチ

最も単純な方法は、1から順に各整数でXを割り、余りがYになるかどうかを確認していくことです。もう一つの方法として、(X − Y)を各整数で割ってみて、「(X − Y)を割り切れるが、Xそのものは割り切れない整数」を解とみなすやり方もあります。本記事ではこの考え方をもとに、C++でプログラムを作成していきます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int numberofdivisor(int X, int Y){
    int N = (X - Y);
    int noOfDivisors = 1;
    for (int i = 1; i <= N/2; i++) {
        // if N is divisible by i
        if ((N % i) == 0) {
            // count if integer is greater than Y
            if (i > Y)
                noOfDivisors++;
        }
    }
    return noOfDivisors;
}
void numberofsolutions(int X, int Y){
    int noOfSolutions;
    if (X == Y)
        noOfSolutions = -1;
    if (X < Y)
        noOfSolutions = 0;
    if (X > Y)
        noOfSolutions = numberofdivisor(X, Y);
    if (noOfSolutions == -1) {
        cout << "X can take Infinitely many values"
        " greater than " << X << "\n";
    }
    else {
        cout << "Number of solution = " << noOfSolutions;
    }
}
// main function
int main(){
    int X,Y;
    cin >> X;
    cin >> Y;
    numberofsolutions(X, Y);
    return 0;
}

実行結果

Xに0を入力すると、プログラムは次のように出力します。

X can take Infinitely many values greater than 0

それ以外の数値を入力した場合の出力は次のとおりです（ここでは5を入力）。

Number of solution = 2

コードの解説

ここからは、プログラムを理解しやすくするために、各関数の役割を順番に見ていきましょう。

main() 関数

main関数では、XとYの値を標準入力から受け取り、numberofsolutions()関数を呼び出すことで、取り得る解の個数を求めています。

numberofsolutions() 関数

この関数は、XとYが条件を満たしているかどうかを判定します。割られる数より大きい余りは存在しないため、XはY以上でなければなりません。XがYより大きい場合はnumberofdivisor()関数を呼び出し、Xを割った余りがYとなる約数の個数を取得します。また、XとYが等しい場合は解が無限個存在するため -1 を返し、XがYより小さい場合は解が存在しないため 0 を返します。

numberofdivisor() 関数

この関数は、1から(X − Y)/2までの範囲でループを実行し、(X − Y)を割り切るすべての整数（約数）を調べます。その中から、Yより大きい整数のみをカウントします。こうして得られた整数は、Xを割ったときに余りYとなる解に対応します。カウントの初期値が1になっているのは、(X − Y)自身もXを割ると余りYになる約数だからです。

まとめ

モジュラ方程式の解とは、「Xを割ったときに余りがYとなる整数」のことです。記事内の複数の例を通じて、この概念を確認しました。解の個数は、(X − Y)の約数のうちYより大きいものを数えるというシンプルなアプローチで効率的に求められます。

今回はC++で実装しましたが、同じロジックはC、Java、Pythonなど、ほかのプログラミング言語でも同様に記述できます。この記事が、モジュラ方程式の解の個数を求める手法を理解する一助となれば幸いです。