(c++) BOJ 1629번: 곱셈

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

1629번: 곱셈

 

 

---

 

 

 

문제 개요

 

 

숫자의 제곱에 대해서 재귀로 프로그램을 돌렸을 경우 O(N)이 걸린다.

ex) n = 6

6 → 5 → 4 → 3 → 2 → 1

 

여기서 분할 정복을 사용한다면 O(logN)이 걸리게 된다.

ex) n = 6

6 → 3  → 2 → 1

 

시간을 절반 정도 줄일 수 있는 분할 정복을 알기에는 최적의 문제인 것 같다.

 

 

코드

 

 

pow() 함수를 사용하지 않았다. (사용하지 않아도 되는 코드이다.)

 

코드가 짧지만 분할 정복의 정수가 담겨있다.

 

n이 짝수일 경우 n / 2로 재귀하고, n이 홀수일 때는 n-1로 재귀하고 숫자를 하나 곱해준다.

 

예시로 n = 11일 때

11 → 10 → 5 → 4 → 2 → 1

계산은 역순으로 시작되어 거듭제곱을 하지 않아도 되게 된다.

 

#include <bits/stdc++.h>

using namespace std;

int a, b, c;

long long mult(long long x) {
    x = x % c;
    x = x * x;
    return x % c;
}
long long return_n(int n) {
    if (n == 1) return a;
    if (n % 2 > 0) return return_n(n - 1) * a;
    return mult(return_n(n / 2));
}

int main(void) {
    cin >> a >> b >> c;
    cout << return_n(b) % c;
}