[BOJ/백준][Silver1] 1629 : 곱셈 (C++)

 

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

1629번: 곱셈

 

 

 

[난이도] Silver1
[유형] 분할정복

[풀이]
A를 B번 곱해야 하는데 B의 범위가 int의 최댓값 까지이므로 직접 곱해서는
시간내에 해결이 불가능합니다.
그러므로 A^2n = A^n*A^n인 거듭제곱의 성질을 이용한 분할정복으로 문제를 해결할 수 있습니다.

각 재귀 호출 sol(n)에서 sol(n/2)을 호출하여 이 값을 제곱해주고
만약 n이 홀수인경우 이 값에 A를 추가로 한번 더 곱해준 값을
리턴해주면 O(lgN)의 시간복잡도로 답을 구할 수 있습니다.

A의 최댓값 역시 int의 최댓값 까지이므로 연산시 오버플로우 방지를 위해 long long 자료형을 이용하였습니다.

 

 

#include <cstdio>
using ll = long long;
ll A,B,C;
ll sol(ll n){
    if(n==1) return A; 
    ll ret = sol(n/2);
    ret = (ret*ret)%C;
    if(n%2) ret=(ret*A)%C;
    return ret;
}
int main(){
    scanf("%lld%lld%lld",&A,&B,&C);
    printf("%lld",sol(B)%C);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/1629.cpp