[알고리즘] 백준 1629

백준 1629번

해결 과정 요약

mod 거듭제곱 연산을 구현하는 문제이다.
2의 거듭제곱은 mod 연산을 통해 구하기 매우 간단하다.
따라서
B를 2의 거듭제곱으로 여러개로 쪼개서 각각을 mod 연산 한 후 스택에 쌓는다.
스택에 있는 값들을 꺼내면서 다시 mod 연산 하는식으로 코드를 작성했다.

풀이

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

long long A,B,C,ret;
vector<long long> v;

void cal(long long n){
    if(n==0) return;
    long long num = A;
    long long i=1;
    for(; i*2<=n; i*=2){
        num = num*num%C;
    }
    v.push_back(num);
    cal(n - i);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> A >> B >> C;
    A = A % C;
    cal(B);
    ret = v[0];
    if(v.size() > 1){
        for(int i=1; i<v.size(); i++){
            ret = ret*v[i]%C;
        }
        cout << ret << "\n";
    }
    else{
        cout << v[0] << "\n";
    }
    return 0;
}

트러블슈팅

• 처음에 주어진 B를 2로 나누어가며 mod 연산을 하였으나 B의 값, B를 2로 나눈 값 등에 따라 여러 분기를 만들어냈다. 이 여러가지 경우의 수를 모두 따지기가 번거로웠다.
  • 역으로 생각하여 B를 2의 거듭제곱수로 표현하는 방식으로 해결.