백준 1629 (곱셈) c++

문제

1629번: 곱셈

a를 b번 곱한 값에 c로 나눈 나머지를 구하는 문제입니다.

a와 b와 c는 최대 2^31 - 1의 값을 가질  수 있는 자연수입니다.

 

먼저 문제를 단순화 하면 a^b % c를 구하면 됩니다.

단순히 a^b를 해버리면 오버플로우가 발생합니다. 

따라서 모듈러 연산을 해줘야 합니다.

 

하지만 단순히 a를 b번 거듭제곱을 하게 해주면 시간초과가 납니다.

만약 b가 21억이면 21억번 계산을 해줘야 하기 때문입니다.

 

우리는 다르게 접근해볼 수 있습니다.

지수 법칙을 이용하는 것입니다.

a^4 = a^2 * a^2 입니다.

a^2 = a^1 * a^1 입니다.

즉 a^4 = (a^1 * a^1 * a^1 * a^1) 

따라서 분할정복을 이용하면 O(log n)의 시간복잡도로 해결이 가능합니다.

 

여기서 중요한점이 지수가 짝수이면 그냥 계속 2를 나눠 주면 됩니다.

하지만 홀수는 따로 처리해줘야 합니다.

빨간색 부분을 보면 굳이 분할정복을 통해 탐색할 필요가 없습니다. 이미 우리가 계산이 되있기 때문입니다.

이미 계산된 곳에 a를 곱해주면 됩니다.

int recur(int ex){
	if(ex == 1)
    		return a;
    long temp = recur(ex / 2) //짝수
    if(ex % 2 == 1)return (temp * temp * a); //홀수
    return temp * temp;
}

이제 모듈러 법칙을 적용해줘야 합니다.

(a * b) % c = ((a % c) * (b % c)) % c

 

if (ex % 2 == 1)return (temp * temp * a) % c;

여기서 만약 a와 b 모두 2^31 -1 이라면 long 형으로 오버플로우가 발생합니다.

temp * temp를 x로 치환 하면

(x * a ) % c가 됩니다. 이를 정리하면

(x * a) % c = ((x % c) * (a % c)) % c가 됩니다.

if (ex % 2 == 1)return ((temp * temp % c) * a % c) % c;

따라서 모두 모듈러 법칙을 적용하면 아래와 같습니다.

int recur(int ex) {
	if (ex == 1)
		return a % c;

	long temp = recur(ex / 2);
	if (ex % 2 == 1)return ((temp * temp % c)* a % c) % c;
	return temp * temp % c;
}

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int a, b, c;
int recur(int ex);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    
    cin >> a >> b >> c;
    
    cout<<recur(b);
 
    
    return 0;
}
int recur(int ex) {
    if (ex == 1)
        return a%c;
 
    long temp = recur(ex / 2);
    if (ex % 2 == 1)return ((temp * temp %c)* a%c)%c;
    return temp * temp%c;
}