[백준 - 1629] 곱셈 [C++]

1. 문제

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

1629번: 곱셈

 

2. 풀이

로직은 맞은채로 계속 틀렸다..

간과하고 있었던 것은 곱셈하면 int 범위를 훨씬 넘어가버린다는 것..

결국 리턴타입을 long long int로 변경해서 해결..

 

이 문제의 핵심 세가지)

1. INT_MAX의 제곱은 long long int 범위에 들어온다.
2. a^5 = a^2 * a^3으로 쪼갤 수 있다.
3. (A * B) % M = ((A % M) * (B % M)) % M;

 

3. 코드

#include <iostream>

using namespace std;

/*
    1. INT_MAX의 제곱은 long long int 범위에 들어온다.
    2. a^5 = a^2 * a^3으로 쪼갤 수 있다.
    3. (A * B) % M = ((A % M) * (B % M)) % M;
*/
long long int solve(int a, int b, int c) {
    // 종료조건
    if(b == 1)
        return a % c;

    // 지수가 짝수라면
    if(b % 2 == 0)
        return ((solve(a, b/2, c) % c) * (solve(a, b/2, c) % c)) % c;

    // 지수가 홀수라면
    else
        return ((solve(a, b/2, c) % c) * (solve(a, b/2 + 1, c) % c)) % c;
}

int main() {
    int a, b, c;

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> a >> b >> c;

    cout << solve(a, b, c);

    return 0;
}