백준 1629번 [곱셈](C++) -yes6686- 티스토리

백준 문제 풀이: 1629 [곱셈]

---

문제 링크: https://www.acmicpc.net/problem/1629

문제 설명:

정수 A, B, C가 주어질 때, A^B를 C로 나눈 나머지를 구하는 문제입니다. 이때, B는 매우 큰 수가 될 수 있으므로 효율적인 계산이 필요합니다.

입력:

• 첫째 줄에 세 정수 A, B, C가 주어집니다. (1 ≤ A ≤ 2,147,483,647, 1 ≤ B ≤ 2,147,483,647, 2 ≤ C ≤ 2,147,483,647)

출력:

• A^B를 C로 나눈 나머지를 출력합니다.

예시:

입력:
10 11 12

출력:
4

---

문제 해결 코드

#include <iostream>
using namespace std;

// A^B % C를 계산하는 함수 (분할 정복 방식)
long long modExp(long long a, long long b, long long c) {
    if (b == 0) return 1; // A^0 = 1
    long long half = modExp(a, b / 2, c); // 절반 계산
    half = (half * half) % c; // (A^(B/2))^2 % C

    if (b % 2 == 1) { // 지수가 홀수인 경우 추가 곱셈
        half = (half * a) % c;
    }

    return half;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long a, b, c;
    cin >> a >> b >> c;

    cout << modExp(a, b, c) << '\n';
    return 0;
}

---

코드 설명

이 코드는 분할 정복을 사용하여 A^B % C를 효율적으로 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 분할 정복:
    • A^B = (A^(B/2))^2로 분할하여 계산합니다.
    • 지수가 홀수일 경우 (A^(B-1)) * A를 추가로 곱합니다.
  • 각 단계에서 모듈러 연산(% C)을 적용하여 값이 커지는 것을 방지합니다.
• 구현 세부사항:
  • modExp(a, b, c): A^B % C를 계산하는 재귀 함수입니다.
  • 기저 사례: B = 0일 때 1을 반환합니다.
  • 재귀 단계: 지수를 절반으로 나누어 계산한 뒤, 결과를 제곱합니다.
• 시간 복잡도 분석:
  • 재귀 호출 깊이: O(log B)
  • 각 호출에서 상수 시간 연산: O(1)
  • 전체 시간 복잡도: O(log B)

---

결과

코드는 매우 큰 B에 대해서도 효율적으로 A^B % C를 계산합니다. 입력 크기가 크더라도 O(log B)의 시간 복잡도로 빠르게 처리할 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!