[BOJ][1629] 곱셈

[ 오늘의 문제 한줄평 ]
return값의 overflow와 더불어 함수 내의 overflow도 신경써야 한다

곱셈

거듭제곱을 divide & conquer로 구하는 것은 잘 했으나, 나머지 정리를 기억하지 못했던 빡대갈쓰

2019년 ACM-ICPC 예선에서도 이와 같은 문제를 나머지 정리가 기억이 안나서 못풀었으니... 앞으로는 제발 좀 기억하도록 하자 ^_^

나머지 정리가 계속 헷갈려서 결국 다른 분의 블로그를 찾아보았고, 정말 정리가 잘 된 블로그를 찾게 되었다.

결론적인 식은 다음과 같다. 이걸 몰라서 그동안 으아아ㅏㄱ

뭐 저거 말고는 여기서 딱히 할건 없ㄷ 라고 말할 자격이 나는 없다. 저 식을 생각해내려고 했던 이유가 거듭제곱을 오지게 하다 보면 long long으로 표현할 수 있는 범위도 넘어갈 수 있는데, 어떻게 거기에다가 mod 연산을 할까? 때문이었다. 근데 뭐 저 나머지 정리 식으로 나머지는 잘 처리했지만, 재귀함수 return 과정에서도 overflow가 발생할 수 있다는 점을 간과하였다.

// overflow 발생한 문제의 코드
return (((solve(A, B / 2, C) % C) * (solve(A, B / 2, C) % C)) * (A % C)) % C;

// 고친 코드
return ((((solve(A, B / 2, C) % C) * (solve(A, B / 2, C) % C)) % C) * (A % C)) % C;

백준 질문 검색은 만능이다. 내가 고민한 문제는 대부분 거기에 있다. 최고

#include <iostream>
using namespace std;

long long solve(int A, int B, int C)
{
    if(B == 1)
        return A % C;
    else if (B == 0)
        return 1;

    if(B%2)
        return ((((solve(A, B / 2, C) % C) * (solve(A, B / 2, C) % C)) % C) * (A % C)) % C;
    else
    {
        return ((solve(A, B / 2, C) % C) * (solve(A, B / 2, C) % C)) % C;
    }
}

int main()
{
    int A, B, C;
    cin >> A >> B >> C;

    // (A^B)%C
    cout << solve(A, B, C);
}