• 문제 : https://www.acmicpc.net/problem/1629

---

1. 문제 접근

• A, B, C 모두 2^31-1까지 가지는 자연수이고, 거듭제곱을 활용하기 때문에 mod연산 + 분할정복까지 고려해야 한다.
• 제한시간이 0.5초이기 때문에, 분할정복을 활용해서 계산해야 한다.

---

2. 시행착오

1. mod 곱셈연산의 수식 헷갈림
2. 동일한 값이 나온 케이스는 저장해서 활용해야, 재귀의 늪에 빠지게 된다.
3. 홀수일 때, 분기 처리 해야 한다는 점

---

3. 코드 및 풀이

3.1 풀이

mod 곱셈연산 : (A * B) mod C = (A mod C * B mod C) mod

• b가 홀수인 경우도 나타날 수 있다. (ex. a = 2, b = 7)
  • 그렇다면 재귀함수를 활용할 때, 2^7 = 2^3 + 2^4와 같은 경우가 생길 수 있음
  • 예외처리 하지 않으면 b는 long long 타입이므로 7/2 = 3이 나와서, 실제로는 2^3 * 2^3만 계산될 수밖에 없다.
  • 이를 처리하기 위해 2^3 * 2 = 2^4를, 즉 a를 한번 더 곱해줘야 한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll A, B, C;
ll tmp, ret;
ll calc(ll a, ll b, ll c){
    if (b == 1) return a % c;

    tmp = calc(a, b/2, c);
    tmp = (tmp * tmp) % c;
    // if b is odd number => only multiple a once
    if (b % 2) {
        return (tmp * a) % c;
    }
    else {
        return tmp;
    }
    
}

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

    ret = calc(A, B, C);
    
    cout << ret << '\n';
    return 0;
}

에러 코드

• b가 홀수인 경우에는 (tmp * tmp * a) * c를 하면 오류가 남
  • 반드시 tmp끼리 mod연산을 해주고, 새로운 tmp와 a를 곱한 후 c와 mod연산을 해야 함
    -큰 수가 나타날 수 있는 지점에 있어서는 모듈러 연산을 해주어야 한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll A, B, C;
ll tmp, ret;
ll calc(ll a, ll b, ll c){
    if (b == 1) return a % c;

    tmp = calc(a, b/2, c);
    // if b is odd number => only multiple a once
    if (b % 2) {
        return (tmp * tmp * a) % c;
    }
    else {
        return (tmp * tmp) % c;
    }
    
    

}

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

    ret = calc(A, B, C);
    
    cout << ret << '\n';
    return 0;
}

---

Reference