[백준] 1629번 곱셈 C++ 문제풀이

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

1629번: 곱셈

문제 풀이

시간 제한이 0.5초이기 때문에 맨 처음에는 규칙을 찾는 문제라고 생각했다. 그러나 규칙을 어떻게 표현할 지, 어떤 식으로 규칙을 통해 답을 낼지 감을 잡지 못해 다른 블로거 분들의 글을 읽어보고 이해했다.

일단 이 문제는 10^11 = 10^(5+5+1) = 10^5 x 10^5 x 10^1 임을 이해하고 문제를 풀어야 하더라...

그리고 재귀를 통해서 지수가 1이 나올때까지 나눠주고 나중에 합치는 방식으로 문제를 해결했다. 

소스 코드

#include <iostream>
using namespace std;

long long A, B, C;

long long Rule(int A, int B, int C) {
    if (B == 1)
        return A % C;

    long long temp = Rule(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 << Rule(A, B, C);
}