a의 b승을 계산해서 c로 나눈 나머지를 구해야 하는 문제다. 어려웠다.
검색해보니까 분할정복으로 풀어야 하는 문제다.
분할정복으로 a의 b승 구현하기
a제곱 b는 아래와 같이 구현할 수 있다.
int pow(int a, int b){
if(b == 0) return 1;
if(b == 1) return a;
if(b%2 == 0) { // 짝수 승이라면,
int temp = pow(a, b/2);
return temp*temp;
}
return pow(a, b-1); // 홀수 승이면 1승 차이.
}pow(a, b)함수로 2의 4승을 연산하려면 pow(2, 4)다.
2의 0 승인 경우, 0승은 항상 1이다.
2의 1승인 경우, 1승은 항상 2이다.
여기서 중요한 건, b가 짝수인 경우다.
2의 4승 == ( 2의 2승 * 2의 2승 )
따라서 b가 짝수라면, b/2승 결과를 구해서 temp에 저장하고, temp를 제곱하면 된다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a, b, c;
ll rec(ll a, ll b){
if(b == 0) return 1;
if(b == 1) return a % c;
long long temp = rec(a, b/2);
if(b%2 == 0){ // b가 짝수라면,
return (temp * temp) % c; // b/2승을 제곱하면 된다.
}
else{// b가 홀수라면, 1번 더 a를 곱해준다.
return ((temp * temp) % c) * a % c;
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> a >> b >> c;
cout << rec(a, b);
return 0;
}
’나머지 구하기'를 제쳐두고 a의 b승을 하면, 숫자가 너무 커져서 long long 으로 연산이 불가능하다.
따라서 ‘a를 c로 나눈 나머지'만 기억하면서 연산해야 한다.
예를 들어, a의 1승은 a % c 가 되어야 한다.
a의 2승은 (a % c) * (a % c) 가 되어야 한다.
2의 4승 == ( 2의 2승 * 2의 2승 ) 임을 이용해서 분할정복으로 구현했다.
짝수 b승을 계산할 때,
b/2 승 * b/2 승을 연산하되, 마지막에는 반드시 c로 나눈 나머지를 저장하자.
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| Hasing 백준 15829번 c++ (0) | 2022.02.11 |
|---|---|
| 시리얼 번호 백준 1431번 c++ (0) | 2022.02.10 |
| 큰 수 A+B 백준 10757번 c++ (0) | 2022.02.09 |
| 피보나치 수 4 백준 10826번 c++ (0) | 2022.02.08 |
| 피보나치 수 5 백준 10870번 c++ (0) | 2022.02.08 |