[BaekJoon 1629번] 곱셈(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

1629번: 곱셈

 

 

[문제 설명]

 

 

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

 

[입력]

 

 

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

 

[출력]

 

 

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

 

[입출력 예]

 

 

입력	출력
10 11 12	4

 

 

[문제 풀이]

 

입력의 범위가 21억이고, 시간 제한이 0.5초로 주어졌기 때문에 일반적으로 생각하는 코드로는 구현하면 안됬다.

 

우선 이 문제를 풀기 위해 생각했던 수학적 개념은 a^n * a^n = a^2n 이였고

1승(a^1)을 계산할 수 있다면, k승(a^k)과 2k승(a^2k), 2k+1승(a^2k+1)도 구할 수 있다는 점이다.

 ↪ 이 부분을 생각할 수 있다면 재귀로 구현이 가능하다.

 

ps. 귀납적 사고를 하자!

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
ull A, B, C;

ull divisional(ull A, ull B, ull C) {
    if(B == 1) {
        return A % C;
    } else {
        ull result = divisional(A, B / 2, C);
        if(B % 2 == 0) 
        {
            return (result * result) % C;
        } else {
            return (((result * result) % C) * A % C);
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> A >> B >> C;
    ull result = 0;
    cout << divisional(A, B, C);
}