C++로 모듈러 방정식의 해 개수 구하는 방법

이 글에서는 모듈러 방정식(modular equation)이 무엇인지, 그리고 모듈러 방정식의 해가 몇 개인지 구하는 프로그램을 작성하는 방법까지 모두 다룹니다. 먼저 가장 기본적인 예시부터 살펴보겠습니다.

입력 : X = 30, Y = 2
출력 : 4, 7, 14, 28
설명 : 30 mod 4 = 2 (Y와 같음),
      30 mod 7 = 2 (Y와 같음),
      30 mod 14 = 2 (Y와 같음),
      30 mod 28 = 2 (Y와 같음)

위 예시에서 알 수 있듯이, X를 어떤 정수로 나누었을 때 나머지가 Y가 되는 모든 정수가 바로 모듈러 방정식의 해입니다. 실제로 30을 4, 7, 14, 28로 나누면 모두 나머지가 2(Y)로 떨어집니다.

해를 찾는 접근 방법

가장 단순한 방법은 1부터 차례대로 모든 정수로 X를 나누어 나머지가 Y인지 확인하는 것입니다. 하지만 이보다 효율적인 방법이 있습니다. 바로 (X − Y)의 약수를 이용하는 것입니다.

X mod i = Y를 만족한다면 X = i × q + Y 형태로 표현할 수 있고, 양변에서 Y를 빼면 (X − Y) = i × q가 됩니다. 즉, i는 반드시 (X − Y)의 약수여야 합니다. 반대로 (X − Y)의 약수 중 Y보다 큰 값은 항상 X mod i = Y를 만족합니다. 따라서 이 문제는 “(X − Y)의 약수 중 Y보다 큰 것의 개수”를 세는 문제로 바꿔 생각할 수 있습니다.

C++ 구현 예제

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

// (X - Y)의 약수 중 Y보다 큰 값의 개수를 반환
int numberofdivisor(int X, int Y){
    int N = (X - Y);
    int noOfDivisors = 1; // N 자신도 항상 약수이므로 1에서 시작
    for (int i = 1; i <= N/2; i++) {
        // N이 i로 나누어 떨어지는 경우
        if ((N % i) == 0) {
            // 약수가 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;
    }
}

// 메인 함수
int main(){
    int X, Y;
    cin >> X;
    cin >> Y;
    numberofsolutions(X, Y);
    return 0;
}

실행 결과

X = 0, Y = 0을 입력하면 X와 Y가 같으므로 해가 무한개라는 메시지가 출력됩니다.

X can take Infinitely many values greater than 0

반면 X = 10, Y = 2를 입력하면 10 mod 4 = 2, 10 mod 8 = 2이므로 해는 4와 8 두 개입니다. 이때 프로그램은 다음과 같이 출력합니다.

Number of solution = 2

코드 상세 설명

각 함수가 어떤 역할을 하는지 하나씩 살펴보겠습니다.

main() 함수

main 함수에서는 X와 Y의 값을 입력받은 뒤 numberofsolutions() 함수를 호출하여 가능한 해의 개수를 구합니다.

numberofsolutions() 함수

이 함수는 해가 존재할 수 있는지 조건을 검사합니다. 나머지는 항상 제수(나누는 수)보다 작아야 하므로 X > Y일 때만 해가 존재합니다. X == Y이면 X보다 큰 모든 정수가 해가 되어 해가 무한개이며(-1로 표시), X < Y이면 해가 하나도 없습니다(0). X > Y인 경우에는 numberofdivisor() 함수를 호출하여 실제 해의 개수를 계산합니다.

numberofdivisor() 함수

이 함수는 N = X − Y에 대해 1부터 N/2까지 반복하면서 N의 약수를 찾고, 그중 Y보다 큰 값만 카운트합니다. 나머지가 Y가 되려면 제수가 반드시 Y보다 커야 하기 때문입니다. 카운트 초기값이 1인 이유는 N 자신(X − Y)이 항상 N의 약수이면서 Y보다 크기 때문에 미리 포함해 두기 위함입니다. 참고로 반복 범위를 √N까지만 탐색하도록 최적화하면 실행 속도를 더욱 개선할 수 있습니다.

마무리

모듈러 방정식의 해란 X를 나누었을 때 나머지가 Y가 되는 정수를 의미하며, (X − Y)의 약수 중 Y보다 큰 값들을 찾으면 됩니다. 이 글에서는 단순 전수 조사보다 효율적인 약수 기반 접근법을 C++ 코드로 구현하고, 각 함수의 동작까지 자세히 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 모듈러 방정식의 해의 개수를 구하는 개념을 이해하는 데 도움이 되기를 바랍니다.