[C++] 1629번 곱셈 - 수학, 분할 정복

#include <iostream>

using namespace std;
typedef unsigned long long int lld;

lld a, b, c;  //A를 B번 곱한 수를 C로 나눈 나머지

lld f(int n)
{
    lld ret;
    
    if(n==1)
        return a;
    else {
        lld tmp = f(n/2)%c;
        ret = tmp*tmp%c;  //분할 정복하기
        if(n%2)  //2로 나눴을 때 나머지가 있으면 a를 한 번 더 곱해야 함
            ret=(ret*(a%c))%c;
        return ret;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);
    
    cin >> a >> b >> c;
    a%=c;
    
    cout << f(b);
    
    return 0;
}

 

여기서 주의 할 점은 분할 정복 과정에서 long long int 범위를 넘어가면 안된다는 것이다. 특히 제곱이라서 해서 pow()함수를 쓰면 안되는데 왜냐하면 pow()함수의 반환 값의 형태는 double이라서 long long int보다 범위가 작기 때문에 오버 플로우가 일어날 수 있기 때문이다. 직접 두 번 곱하자!

 

 

 

 

<C++ pow()>

https://blockdmask.tistory.com/307

[C언어/C++] pow, sqrt 함수에 대해서(루트함수, 제곱, 제곱근)

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.