[C++][백준] 1629 곱셈

이번 문제는 빠른 거듭제곱을 활용하면 쉽고 빠르게 풀 수 있다.

빠른 거듭제곱이 뭘까?

어떤 숫자 x를 n번 거듭제곱 한다고 하면 x를 n번 곱하는 것이 일반적인 계산법이다.

 

예를들어 2의 31제곱을 구해야 한다고 하자. 그렇다면 계산 과정은 아래와 같을 것이다.

2x2x2x2x2x2x2x2x2x2x....x2x2x2x2x2x2x2x2x2x2x2x2x2x2(31번 곱했다고 치자.)

 

이 방법의 경우는 시간복잡도가 O(n)이다. 만약 n이 아주 큰 수라면 계산하는 시간이 오래 걸리게 될 것이다.

 

더 빨리 구하는 방법은 무엇일까?

 

생각을 약간 틀어서 지수인 31을 이진수로 생각해보자. 31 => 11111(2)이다.

 

2^{11111₍₂₎}을 계산한다고 생각하면

2⁴ x 2³ x 2² x 2¹ x 2⁰ 만 계산하면 된다.

 

이 방법의 경우 시간복잡도가 O(logN)이다. 계산 시간이 획기적으로 줄어들었다.

 

logN번의 곱셈으로 an 을 구할 수 있는 것이다.

 

이 알고리즘을 이용해서 문제를 해결해보자.

 

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

코드를 살펴보자

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int ipow( ll a, ll b, ll c){
    if(b == 0) 
    	return 1;
    long long tmp = ipow(a, b/2, c);
    long long ans = (tmp * tmp) % c;
    if(b % 2 == 1) 
    {
        ans *= a;
        ans %= c;
    }
    return ans;
}
int main(){
    long long a,b,c,m;
    cin >> a >> b>> c;
    m = ipow(a,b,c);
    cout << m;
    return 0;
}

• 재귀함수를 사용해서 빠른거듭제곱 알고리즘을 적용했다. ab/2를 계산한다.
• b%2 == 1인 경우 a를 한번 더 곱해준다.
• 혹시나 계산 과정에서 int 범위를 넘어갈 수 있기 때문에 long long형으로 선언해주었다.