C/C++로 구현하는 모듈러 방정식 해의 개수 찾기 프로그램

문제 소개

이번 글에서는 모듈러(나머지) 방정식과 관련된 흥미로운 문제를 다뤄보겠습니다. 두 정수 A와 B가 주어졌을 때, (A mod X) = B를 만족하는 변수 X가 가질 수 있는 값의 개수를 구하는 것이 목표입니다.

예를 들어 A가 26이고 B가 2라고 가정해 봅시다. 이때 조건을 만족하는 X의 후보 값은 {3, 4, 6, 8, 12, 24}이며, 따라서 정답은 6이 됩니다. 핵심 아이디어를 더 잘 이해하기 위해 알고리즘부터 살펴보겠습니다.

핵심 아이디어

(A mod X) = B가 성립하려면, A에서 B를 뺀 값인 N = A − B가 X로 나누어떨어져야 합니다. 즉, X는 반드시 N의 약수여야 하며, 동시에 나머지가 성립하려면 X > B라는 조건도 충족해야 합니다.

특별한 경우는 다음과 같이 처리합니다.

• A == B인 경우: A보다 큰 모든 X에 대해 나머지가 항상 A 자신(B)이 되므로, 해는 무한히 많습니다.
• A < B인 경우: 나머지는 항상 피제수(A)보다 작으므로, 조건을 만족하는 해는 존재하지 않습니다.

알고리즘

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

약수를 셀 때는 1부터 √N까지만 순회하면서 i와 N/i를 함께 확인하므로, 전체 시간 복잡도는 O(√N)입니다. i와 N/i가 같은 경우 중복으로 세지 않도록 주의해야 합니다.

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) // 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 mod X) = B라는 조건을 "A − B의 약수 중 B보다 큰 값의 개수"를 세는 문제로 변환하는 것입니다. 이렇게 하면 모든 X를 일일이 검사하는 대신, 약수만 효율적으로 탐색하여 빠르게 답을 구할 수 있습니다. 특히 A와 B가 같거나 A가 B보다 작은 경계 조건을 반드시 먼저 처리해 주어야 정확한 결과를 얻을 수 있습니다.