Computer >> 컴퓨터 >  >> 프로그래밍 >> C 프로그래밍

C/C++로 모듈러 방정식의 해 개수 구하기

모듈러 방정식이란?

수학에서 모듈러 방정식(modular equation)이란 모둘리 문제(moduli problem)의 관점에서 모듈리(moduli)가 만족하는 대수 방정식을 의미합니다. 즉, 모둘리 공간 위에 정의된 여러 함수들이 주어졌을 때 이들 사이에서 성립하는 방정식, 다시 말해 모듈리에 대한 항등식을 가리킵니다.

모듈러 방정식이라는 용어는 특히 타원 곡선(elliptic curve)의 모둘리 문제와 관련해 가장 널리 사용됩니다. 이 경우 모둘리 공간 자체의 차원은 1이므로, 모듈러 곡선의 함수체에 속한 임의의 두 유리 함수 F와 G에 대해 복소수 계수의 두 변수 다항식 P로 표현되는 모듈러 방정식 P(F, G) = 0이 반드시 성립합니다. 적절한 비퇴화(non-degenerate) 조건으로 F와 G를 선택하면, 방정식 P(X, Y) = 0은 실제로 해당 모듈러 곡선을 정의하게 됩니다.

프로그래밍에서는 다음과 같은 형태의 수학적 표현을 자주 접하게 됩니다.

B ≡ (A mod X)

이는 "B는 A를 X로 나눈 나머지와 동치(congruent)이다"라는 뜻입니다. 예를 살펴보겠습니다.

21 ≡ 5 (mod 4)

기호 ≡는 "동치(equivalence)"를 나타냅니다. 위 식에서 21과 5가 동치인 이유는 21 mod 4 = 1과 5 mod 4 = 1로 나머지가 같기 때문입니다. 또 다른 예로 51 ≡ 16 (mod 7)이 있습니다.

문제 정의

이번 문제에서는 두 정수 A와 B가 주어지며, 모듈러 방정식 (A mod X) = B를 만족하는 X 값의 개수를 구해야 합니다.

예시

입력: A = 26, B = 2
출력: X는 6개의 값을 가질 수 있음

설명

X는 {3, 4, 6, 8, 12, 24} 중 하나가 될 수 있습니다. 26을 이 값들로 나누면 나머지가 모두 2이기 때문입니다. 즉, (26 mod 3) = (26 mod 4) = (26 mod 6) = (26 mod 8) = ... = 2 입니다.

접근 방법

풀어야 할 방정식은 A mod X = B입니다. 먼저 세 가지 경우로 나누어 조건을 분석해 보겠습니다.

  • A = B인 경우: A보다 큰 모든 X에 대해 나머지가 항상 A와 같아지므로, 무한히 많은 해가 존재합니다.
  • A < B인 경우: 나머지는 나누는 수보다 작아야 한다는 원칙에 따라 방정식을 만족하는 X는 존재하지 않습니다.
  • A > B인 경우: 실제 계산이 필요한 경우입니다.

A > B인 경우에는 나눗셈의 기본 관계식을 활용합니다.

피제수(Dividend) = 제수(Divisor) × 몫(Quotient) + 나머지(Remainder)

여기서 피제수는 A, 나머지는 B이며, 제수가 바로 우리가 구하고자 하는 X입니다. 이를 정리하면 다음과 같습니다.

A = X × 몫 + B

몫을 Y라고 표현하면,

∴ A = X × Y + B
∴ A − B = X × Y

Y가 정수가 되려면 X가 (A − B)를 나누어 떨어지게 해야 합니다.

∴ X는 (A − B)의 약수여야 한다

핵심은 (A − B)의 약수를 찾는 것이며, 그중 조건을 만족하는 약수의 개수가 곧 X가 가질 수 있는 값의 개수입니다.

한 가지 더 고려할 점이 있습니다. 나머지 연산의 결과는 항상 0부터 X − 1 사이의 값이므로, 나머지가 B가 되려면 X > B를 만족해야 합니다.

따라서 결론은 다음과 같습니다. (A − B)의 약수 중 B보다 큰 값들의 개수가 곧 A mod X = B를 만족하는 X의 모든 가능한 값의 개수입니다.

C++ 구현 예제

#include <iostream>
#include <math.h>
using namespace std;
int Divisors(int A, int B) {
    int N = (A - B);
    int D = 0;
    for (int i = 1; i <= sqrt(N); i++) {
        if ((N % i) == 0) {
            if (i > B)
                D++;
            if ((N / i) != i && (N / i) > B)
                D++;
        }
    }
    return D;
}
int PossibleWaysUtil(int A, int B) {
    if (A == B)
        return -1;
    if (A < B)
        return 0;
    int D = 0;
    D = Divisors(A, B);
    return D;
}
int main() {
    int A = 26, B = 2;
    int Sol = PossibleWaysUtil(A, B);
    if (Sol == -1) {
        cout <<" X can take Infinitely many values greater than " << A << "\n";
    } else {
        cout << " X can take " << Sol << " values\n";
        return 0;
    }
}

코드 설명

Divisors 함수는 (A − B)의 약수를 효율적으로 찾기 위해 1부터 √N까지만 순회합니다. 약수는 쌍으로 존재하기 때문에 i가 약수이면 N/i도 약수이며, 두 값 모두 B보다 클 때만 카운트를 증가시켜 중복 없이 정확한 개수를 구할 수 있습니다. PossibleWaysUtil 함수는 A = B(무한대), A < B(해 없음), A > B(약수 개수 계산)의 세 경우를 처리합니다.