백준 [1629] "곱셈"

곱셈 문제는 모듈러 연산을 이용해 해결하는 문제이다. A를 B번 곱하고 C번 나누는 것을 생각없이 진행하게 되면 입력 상한선에 의해 시간 초과가 일어나게 된다.

그렇기에 연산을 무식하게 진행하지 않고 재귀적으로 풀어나가야 한다.

#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;
}

모듈러 연산에서 지수가 짝수일때는 temp temp % C;를 진행한다. 그렇기 때문에 B%2==0일 경우는 temp temp % C;의 결과인 temp를 return하고 홀수일 경우에는 temp * A % C를 진행한다.

b를 짝수 일 때, 홀수 일 때를 나눠서 생각해본다. 2^10이면 b가 짝수인데, 2^10 = 2^5 2^5이고 2^5 = 2^2 2^2 2이고 2^2 = 2 2 임을 생각해본다.
설명 참조