[C++][백준] 11819 The Shortest does not Mean the Simplest

1629번 곱셈 문제와 동일하지만 수 범위가 더 큰 문제이다.

문제

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

 

입력

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

 

출력

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

 

<곱셈 글 보러가기>

자세한 설명은 여기 있으니 관심있다면 한번 보도록 하자.

https://cromcode.tistory.com/15

 

코드를 살펴보자

#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
__int128_t ipow(ull a, ull b, ull c){
    if(b == 0) return 1;
    __int128_t tmp = ipow(a, b/2, c);
    __int128_t ans = (tmp * tmp) % c;
    if(b % 2 == 1) {
        ans *= a;
        ans %= c;
    }
    return ans;
}
int main(){
    ull a,b,c,m;
    cin >> a >> b>> c;
    m = ipow(a,b,c);
    cout << m;
}

• 숫자 범위가 1018이므로 long long 범위를 벗어난다.
• 그래서 __int128을 사용해서 범위만 늘려주면 된다.