백준 11819번 C++ 풀이

https://www.acmicpc.net/problem/11819

11819번: The Shortest does not Mean the Simplest

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	실버1

문제

Your are given integer numbers A, B and C. Output the remainder of division A^B (B-th power of A) by C .

입력

The only line of the input file contains three integers: A, B, C (1 ≤ A,B,C ≤ 10^18). Numbers are separated by spaces.

출력

Output must contain only one non-negative integer less than C the answer to the problem.

---

https://codejin.tistory.com/114 

백준 1629번 C언어 풀이

이 문제의 연장선상에 놓인 문제이다. A^B mod C를 출력하는 문제이지만, B의 값이 너무 크기 때문에 단순히 반복문을 돌렸다가는 시간초과가 나게 된다. 따라서 분할 정복을 통해 시간을 줄여야 한다.

 

또한 입력범위가 1629번 문제보다 더 큰 10^18인데, 이는 2^60보다 조금 더 큰 정도로, long long형을 사용해야한다고 착각하는 순간 틀리게 된다. 백준의 채점서버와 필자가 사용하는 gcc계열의 컴파일러는 __int128_t라는 -2^127 ~ 2^127 - 1까지 담을 수 있는 정수형이 있다. (비주얼 스튜디오에서는 안되는 것으로 알고 있다). 이를 통해 10^18 * 10^18을 담을 때 일어날 오버플로우를 막아야 한다.

 

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

uint64_t sol(__int128_t a, __int128_t b, __int128_t mod){
    if (!b) return 1;
    else if(b == 1) return a;
    else {
        __int128_t ret = sol(a, b/2, mod);
        if(b & 1) return (a * ((ret * ret) % mod)) % mod;
        else return (ret * ret) % mod;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    uint64_t a, b, mod;
    cin >> a >> b >> mod;
    cout << sol(a % mod, b, mod);
}

 

형을 제대로 맞추지 못해 받은 무수한 오답들