[백준][1629번] 곱셈[cpp, c++]

백준 1629 곱셈

• 재귀로 풀어야 풀 수 있는 문제이다.
• 재귀에 약한 나는 고생을 많이 했다 ㅠ
• https://www.acmicpc.net/problem/1629

1629번: 곱셈

• 풀이 방법
  1) 이 문제의 시간제한은 2초이다. 1초에 3~5억 번의 연산을 한다고 가정하면, 2초는 10억 번 안에 연산을 끝내야 한다.
  2) 최악의 경우 O(n)이라면, 문제의 주어진 수가 최대 21억이기 때문에 시간 초과가 뜨게 된다.
  3) 즉, O(n) 보다 낮은 알고리즘을 이용해한다.
  4) b를 짝수 일 때, 홀수 일 때를 나눠서 생각해본다. 2^10이면 b가 짝수인데, 2^10 = 2^5 * 2^5이고
  2^5 = 2^2 * 2^2 *2이고 2^2 = 2 *2 임을 생각해본다.
  5) 즉 b를 계속 2를 나누게 되어 연산하고, 연산한 값을 변수에 저장하고 계산한다면 시간 복잡도는 O(logn)이 된다.

 #include<iostream>

using namespace std;
long long A, B, C;
long long POW(int A, int B, int C) {
    if (B == 0) return 1;
    long long temp = POW(A, B/2, C);
    temp = temp * temp % C;
    if (B % 2 == 0) return temp; //짝수 일때
    else return temp * A % C; //홀 수 일때

}


int main(void) {
    cin >> A >> B >> C;
    cout << POW(A, B, C);
    return 0;
}