백준 1629

* 출처 : [10주완성 C++ 코딩테스트 | 알고리즘 IT취업]

* 조건

▶ 자연수 A를 B번 곱한 수를 알고 싶다
▶ 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램 작성할 것
▶ 첫째 줄 A, B, C가 빈칸을 사이에 두고 순서대로 주어짐
▶ A, B, C 모두 2,147,483,647 이하의 자연수

* 중요한 점

▶ 단순한 곱셉문제가 아님(최대, 최소 확인)
▶ A와 B는 20억 이하(A*B를 단순히 곱하면 엄청나게 커짐)

• 변수(A)에 담아 놓고 풀이

  2^4 = 2^2 2^2
  2^8 = 2^4 2^4

2^4 = A로 두고 2^8은 A * A

▶ go(2, 64) => 2를 64번 곱한다는 의미
=>go(2, 32) => go(2, 16) => go(2, 8) => go(2, 4) => go(2, 2) => go(2, 1)
▶ 6번(log2^64)

▶ 모듈연산
(a+b)%c = a%c + b%c

▶ 20억 범위는 int 범위를 넘어감 -> long long
▶ 곱할 때마다 범위가 더 커짐(매번 곱할 때마다 % c를 적용함)

* 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;
ll go(ll a, ll b) {
    if(b == 1) return a % c;
    ll ret = go(a, b / 2);
    ret = (ret * ret) % c;
    if(b % 2)ret = (ret * a)%c;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
    cin >> a >> b >> c;
    cout << go(a, b) << "\n";
    return 0;
}

* 정리

1) ll go(ll a, ll b) : int의 크기를 벗어나므로 long long 사용

2) 재귀함수는 기저사례( if(b == 1) return a % c;)가 필요
▶ b가 1일 때 1을 리턴

3) 2^5 = 2^4 2^1 = 2^2 2^2 2^1 (홀수의 경우, 2^1을 한 번 더 곱할 것) ▶` if(b % 2)ret = (ret a)%c;`(홀수라는 의미)

▶ C++은 0은 false, 나머지는 true => if(0) = false라는 의미