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

C++에서 매우 큰 수의 거듭제곱 나머지 (a^b)%m 구하기

개요

이 튜토리얼에서는 a가 매우 큰 숫자일 때 (ab)%m을 구하는 방법을 알아보겠습니다. 여기서 a는 일반적인 정수 자료형에 담을 수 없을 만큼 크기 때문에 문자열 형태로 주어진다고 가정합니다.

모듈러 연산의 성질을 활용하면 이 문제를 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

(ab)%m = ((a%m) × (a%m) × ... )%m  (b번 반복)

즉, 먼저 a%m 값을 구한 뒤, 그 결과를 b번 곱하면서 매번 m으로 나머지 연산을 적용하면 오버플로우 없이 정답을 얻을 수 있습니다.

해결 접근 방법

  • 숫자 a(문자열), 지수 b, 모듈러 값 m을 초기화합니다.

  • a%m을 구하는 함수를 작성합니다.

    • 결과값을 0으로 초기화합니다.

    • 문자열 형태의 숫자를 왼쪽부터 한 자리씩 순회합니다.

    • 각 자릿수를 결과값에 추가합니다.

    • 매 단계마다 결과값을 mod로 나눈 나머지로 갱신하여 값이 커지지 않도록 합니다.

  • a%m의 최종 값을 구합니다.

  • b번 반복하는 루프를 작성합니다.

    • 매 반복마다 (현재 결과 × a%m) % m을 계산합니다.

  • 최종 결과를 출력합니다.

예제 코드

위 접근 방식을 C++ 코드로 구현하면 다음과 같습니다.

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

// 문자열로 표현된 큰 수 a를 mod로 나눈 나머지를 구하는 함수
unsigned int aModm(string str, unsigned int mod) {
    unsigned int number = 0;
    for (unsigned int i = 0; i < str.length(); i++) {
        number = number * 10 + (str[i] - '0');
        number %= mod;
    }
    return number;
}

// (a^b) % m을 구하는 함수
unsigned int aPowerBmodM(string &a, unsigned int b, unsigned int m) {
    unsigned int a_mod_m_result = aModm(a, m);
    unsigned int final_result = 1;
    for (unsigned int i = 0; i < b; i++) {
        final_result = (final_result * a_mod_m_result) % m;
    }
    return final_result;
}

int main() {
    string a = "123456789012345678901234567890123";
    unsigned int b = 3, m = 7;
    cout << aPowerBmodM(a, b, m) << endl;
    return 0;
}

출력 결과

위 프로그램을 실행하면 다음과 같은 결과를 얻습니다.

1

동작 원리

aModm 함수는 문자열로 표현된 거대한 숫자를 왼쪽부터 한 자리씩 처리합니다. 기존 결과에 10을 곱하고 새 자릿수를 더한 뒤, 즉시 mod로 나머지 연산을 수행하기 때문에 어떤 크기의 숫자라도 오버플로우 없이 나머지를 구할 수 있습니다.

aPowerBmodM 함수는 앞서 구한 a%m 값을 밑(base)으로 사용하여 b번 곱셈을 반복합니다. 곱셈 후마다 %m을 적용하므로 중간 결과가 항상 m보다 작게 유지됩니다.

시간 복잡도

aModm 함수는 문자열 길이 n에 대해 O(n) 시간이 걸리고, 거듭제곱 계산은 O(b) 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(n + b)입니다. 참고로 b가 매우 큰 경우에는 빠른 거듭제곱(모듈러 지수 연산)을 사용하면 O(log b)까지 최적화할 수 있습니다.

마무리

이 튜토리얼에서는 문자열로 주어진 매우 큰 수의 거듭제곱 나머지를 구하는 방법을 배웠습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.