백준 1629 - 곱셈

문제

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

1629번: 곱셈

 

풀이

A를 B번 곱한후 C로 나누는 시도를 하면 시간도 초과할 수 있고, 연산 값도 엄청나게 커져서 결과가 제대로 안나온다. B가 엄청나게 커지면 곱셈하는데 시간을 다 소모하게 된다. 다음과 같은 나머지 연산에 대한 공식이 있다.

A * B % C = (A % C) * (B % C) % C 

 

그리고 곱셈 연산의 수를 줄이기 위해 다음과 같은 규칙을 이용한다.

10 ^ 10 = (10 ^ 5)의 제곱 , 지수가 짝수일 경우

10 ^ 11 = (10 ^ 5)의 제곱 * 10 , 지수가 홀수일 경우

이 규칙을 이용하면 곱셈 연산의 회수를 대폭 줄일 수 있다.

 

위의 공식과 규칙을 이용하여 문제를 해결한다. power(num, n) 함수를 이용한다. num에는 곱할 수를 n에는 지수를 넣어준다. n/2를 반복해서 해주면서 문제를 분할한다. n%2 == 0 이면 지수가 짝수이다. 지수가 짝수일때는 tmp * tmp % C를 해주면 된다. n%2 == 1이면 지수가 홀수이다. 지수가 홀수 일때는 짝수인 경우인 tmp * tmp % C 뒤에 * num % C가 남아있으므로 함께 계산해주면 된다.

 

코드

#include <iostream>
using namespace std;
 
int A, B, C;
 
long long power(int num, int n)
{
    if (n == 0) return 1;
 
    long long tmp = power(num, n / 2);
    
    if (n % 2)
        return ((tmp * tmp) % C) * num % C;
    else
        return (tmp * tmp) % C;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> A >> B >> C;
    cout << power(A, B);
 
    return 0;
}