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

분류: 수학, 재귀, 분할 정복 /

 

문제

문제 링크

문제 설명

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

입력

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

출력

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

 

풀이

#include <iostream>
using namespace std;

int base, m;

int POW(int e) {
    if(e == 1) return base % m;
    long long val = POW(e/2);
    val = val * val % m;
    if(e & 1) val *= base;
    return val % m;
}

int main() {
    int e; 
    cin >> base >> e >> m;
    cout << POW(e);
}

귀납

• 1승을 계산할 수 있다.
• k승을 안다면 2k와 2k+1을 계산할 수 있다.

따라서, f(n)은 f(n/2)로 계산 가능하다.