https://www.acmicpc.net/problem/11819
시간 제한 | 메모리 제한 | 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.
이 문제의 연장선상에 놓인 문제이다. 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);
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 4796번 C++ 풀이 (0) | 2022.01.26 |
---|---|
백준 2870번 C++ 풀이 (0) | 2022.01.25 |
백준 5585번 C++ 풀이 (0) | 2022.01.21 |
백준 1018번 C++ 풀이 (0) | 2022.01.21 |
백준 1436번 C++ 풀이 (0) | 2022.01.20 |