백준 1692 곱셈 c++ [컴공과고씨]

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

1629번: 곱셈

 

문제 간단 정리

정말 간단하다

a,b,c가 주어짐.

a^b을 구하는 문제임.

단 a^b값이 너무 클 수 있으니 c로 나눈 나머지를 구하면됨.

 

문제 해결 방법

일단 나머지 정리를 알아야함.

나머지 정리는 그냥 간단하게 그냥 ((a%c) * (b%c) %c) 하고 (a*b)%c 같다. 

즉, 이런 문제가 나오면 그냥 나머지 구하고 곱해주고 나머지 구해주면 된다.

 

제한 시간이 2초이기 때문에 1초에 3~5억번 연산을 한다고 했을 때 문제의 주어진 수가 최대 21억이기 때문에

무작정 하나하나 곱해주게 되면 시간 복잡도가 O(n)이기 때문에 시간 초과가 난다.

그래서 이 문제는 분할 정복(divide and conquer)을 사용해야한다.

원리는 이거다 a^8 = a*a*a*a*a*a*a*a 이면 연산을 8번해야하는데

이걸 ((a^2)^2)^2 으로 바꾸어주면 3번의 연산으로 처리할 수 있게 된다.

그래서 재귀 함수를 이용해서 b/2로 넣어주고 b=0일 때는 1을 리턴해준다.

그리고 임시 변수 temp에 함수 리턴값을 넣어주고 그럼 이 리턴 값이 a^(b/2)가 될것이니

이것을 (a^(b/2))^2 해주는것을 반복해주면 된다. 

 

주의할점은 b/2가 홀수 일 경우 리턴 값을 a하나를 더 곱해주어야한다.

예를 들면 2^5 -> 2^2 * 2^2 * 2 이런식으로 말이다.

 

전체코드

#include <iostream>
using namespace std;
long long mt(long long a, long long b, long long c){
    if(b == 0) // a^0 일때
        return 1; // 1을 리턴해주고
    long long temp = mt(a, b / 2, c); //c^(b/2) 을 구해주고
    temp = (temp * temp) % c; // (c^(b/2))^2 꼴로 해줌 
    if (b % 2 == 0) // b가 짝수일 경우
        return temp; // 계산된거 리턴
    else // 홀수인 경우는 남은거 하나 곱해주어야함. 
        return (temp*a)%c; 
}
int main(){
    long long a, b, c;
    cin >> a >> b >> c;
    long long result = mt(a, b, c);
    
    cout << result;
    return 0;
}