[Algorithm] Baekjoon 1629번 : 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

#define ull unsigned long long
 
ull a, b, c;
 
ull pow(ull b) 
{
    if (b == 0) return 1;
    if (b == 1) return a % c;
 
    ull t = pow(b / 2) % c;
 
    if (b % 2 == 0) return t * t % c;
    return t * t % c * a % c;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> a >> b >> c;
 
    cout << pow(b);
}

브루트포스방식으로 해결한다고 가정했을 때 2가지의 문제점이 생긴다.

 

1. 자료형의 범위를 넘어서는 큰 수가 발생할 수 있어서, 정상적인 최종적인 값 출력이 불가능.

2. 연산횟수가 너무 많기때문에 시간초과.

 

 

먼저 1번을 해결하기위해서는 나머지연산을 사용해야 한다. 

알고리즘문제에서는 나머지연산을 사용하는 문제들이 자주 나오기 때문에 아래의 공식정도는 알고 있어야 한다.

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

(A / B) % p = (A * B^(p-2)) % p = ((A % p) * (B^(p-2) % p)) % p

일단 위 공식을 숙지한 채로, 2번을 해결해보자.

 

2번같은 경우는 c도 최대 21억...(int형 최대값)이기 때문에 연산횟수를 반드시 줄여줘야한다.

아래의 식처럼 분할정복개념으로 접근하면, logN 으로 처리가 가능하다.

 

a^b == a^(b/2) * a^(b/2)        // b가 짝수일 경우.

a^b == a^(b/2) * a^(b/2) * a  // b가 홀수일 경우. 

 

홀수일 경우, a^(b/2) * a^(b/2 + 1) 도 맞지만, 그러면 a^(b/2 + 1)에 대해서 재귀가 또 돌아야하기 때문에 미리 기록해둔값인 a^(b/2)을 재활용할 수 있게 식을 표현한것이다.

바로 위의 a^b공식을 제일 위의 곱셈에 대한 나머지연산공식에 대입하면 위의 코드처럼 나오게 된다.