백준 1629번 : 곱셈

  분할 정복 시리즈의 4번째 문제다. 사실 분할 정복...보다는 그냥 수학문제에 가깝지 않나 싶다. 일단 기본 개념은 다음과 같다.

기본 개념과 관련된 식

 

이 식은 x를 y로 나눈 나머지라는 뜻이다. 나머지를 티스토리 수식으로 어떻게 쳐야할지 몰라서...ㅠㅠ 이 수식에 대한 증명은 시간이 남으면 그때 추가로 달 생각이다.

 

  아무튼 이 문제의 요지는 어떻게 큰 숫자들을 잘 관리할 것인가 + 재귀로 진행했을 때 지수의 값이 클수록 엄청난 메모리가 소비되는데 이것을 어떻게 할 것이냐 이다. 문제에서 b가 21억으로 주어질 수도 있기 때문에 단순한 brute force로는 할 수 없다. 따라서 절반으로 나눠가면서 진행했다. 또한 최초에 a를 그냥 넣지 않고 한 번 c로 나눈 나머지로 바꿔줘야 한다. 기본 연산자는 메모리나 연산 속도에 전혀 영향을 미치지 않으니 divider로 나눈 나머지를 수시로 해줘서 숫자가 너무 커지지 않게 방지해주는 것도 잊지 말자!

 

#include <iostream>
#include <stdio.h>

using namespace std;

int a, b, c;

long long dividePower(int base, int exponent, int divider)
{
    if(exponent == 1) return base;
    
    long long half = dividePower(base, exponent / 2, divider);
    
    if (exponent % 2 == 0) return half * half % divider;
    else return (half * half % divider) * base % divider;
}

int main()
{
    cin >> a >> b >> c;
    a %= c;
    cout << dividePower(a, b, c);
}