[BOJ] 1629번 | 곱셈 (C++)

🔗문제 보러가기

1629번: 곱셈

 

🧑🏻‍💻풀이 과정

처음 문제를 봤을 때는 문제가 원하는 게 뭐길래 실버 1일까 생각했는데, 주어진 숫자 범위가 모두 최대 2,147,483,647이더군요... 즉, \(O(n)\) 알고리즘으로 작성하게 되면 최대 2,147,483,647(21억) 번 돌기 때문에, 시간 내로 절대 못 통과합니다.

 

\( O(logN) \) 정도는 되어야 풀 수 있을텐데, 어떻게 할까 하다가 저는 2개씩 묶는 방법을 선택하였습니다.

2개씩 묶게 되면, 다음 두 가지 상황을 직면하게 됩니다.

• B가 짝수일 경우  \( \rightarrow \)  남는 것 없이 모두 묶이므로 그대로 진행
• B가 홀수일 경우  \( \rightarrow \)  1개가 남으므로, 별도로 곱해주기

 

가령 6을 11번 거듭제곱해야 하는 상황을 예시로 들어보겠습니다.

6 6 6 6 6 6 6 6 6 6 6

 

6을 두 개씩 묶으면 총 5개로, 6이 하나가 남는 상황이 됩니다.

(6 6) (6 6) (6 6) (6 6) (6 6) 6

 

즉, \( 6 \times 6 = 36 \)이 5개가 생기게 됩니다. 하나 남은 6은 별도로 곱해주기로 하고, 36을 다시 두 개씩 묶습니다.

그러면 \( 36 \times 36 = 1296 \)이 2개가 생기게 되고, 36이 하나 남게 됩니다.

(1296) (1296) 36

 

마찬가지로 36도 나중에 별도로 곱해주기로 하고, 다시 2개씩 묶어보겠습니다.

2개 남았으므로 1개밖에 생성되지 않습니다.

1679616

 

이 숫자에 아까 별도로 남았던 6, 36을 곱해주면 거듭제곱 최종 결과가 나오게 됩니다.

1679616 * 6 * 36

 

물론 오버플로우가 되지 않도록, 중간 연산 과정마다 % C를 해주는 것을 잊지 말아야 합니다.

이러한 과정을 반복하여 답을 구할 수 있습니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;
using uint64 = unsigned long long;

uint64 Pow(uint64 A, int B, const int C)
{
    if (B <= 1)
        return A % C;  // (A:4, B:1, C:2)와 같은 입력도 존재하므로

    int numCount = B / 2;
    int mod = B % 2;

    uint64 square = (A * A) % C;
    uint64 modNum = (mod == 0) ? 1 : A;
    
    return (modNum * Pow(square, numCount, C)) % C;
}

int main()
{
    FAST_IO
    int A, B, C;
    cin >> A >> B >> C;

    uint64 answer = Pow(A, B, C);
    cout << answer;
    return 0;
}