BOJ 1629: 곱셈

✔ 문제 링크

BOJ 1629: 곱셈

---

✔ 문제해결전략

• Recursion

---

✔ 해결과정

exponent가 거의 INT_MAX에 근접하므로 일일이 b 번 곱하고 있으면 당연히 시간 초과가 날 것이다. 다음과 같이 modular 연산의 성질과 지수 법칙을 이용하면 exp/2를 계속 재귀 호출하면서 O(log N)으로 바운드 시킬 수 있다.

a^exp × a^exp = a^(2*exp)

a mod n * b mod n = (a * b) mod n

---

✔ 정답 CODE

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


ll multi(ll x, ll y, ll z) {
    if(y==1) return x % z;
    ll ans = multi(x, y/2, z);
    ans = ans * ans % z;
    // y == odd
    if(y&1) return x * ans % z;
    // y == even
    return ans % z;

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll a, b, c;
    
    cin >> a >> b >> c;
    cout << multi(a, b, c);
}

---

✔ Check Point

지수가 짝수인지 홀수인지를 여부를 체크하기 위해 modular(%) 연산 대신 bitwise and(&) 연산을 사용했다. 1의 경우 LSB만 1이고 나머지 bit은 모두 0이므로 1과 bitwise and(&) 결과가 1이면 홀수, 0이면 짝수다. bitwise 연산의 cost가 더 적다는 것은 당연