728x90
반응형
1. 문제
https://www.acmicpc.net/problem/1629
2. 풀이
로직은 맞은채로 계속 틀렸다..
간과하고 있었던 것은 곱셈하면 int 범위를 훨씬 넘어가버린다는 것..
결국 리턴타입을 long long int로 변경해서 해결..
이 문제의 핵심 세가지)
1. INT_MAX의 제곱은 long long int 범위에 들어온다.
2. a^5 = a^2 * a^3으로 쪼갤 수 있다.
3. (A * B) % M = ((A % M) * (B % M)) % M;
3. 코드
#include <iostream>
using namespace std;
/*
1. INT_MAX의 제곱은 long long int 범위에 들어온다.
2. a^5 = a^2 * a^3으로 쪼갤 수 있다.
3. (A * B) % M = ((A % M) * (B % M)) % M;
*/
long long int solve(int a, int b, int c) {
// 종료조건
if(b == 1)
return a % c;
// 지수가 짝수라면
if(b % 2 == 0)
return ((solve(a, b/2, c) % c) * (solve(a, b/2, c) % c)) % c;
// 지수가 홀수라면
else
return ((solve(a, b/2, c) % c) * (solve(a, b/2 + 1, c) % c)) % c;
}
int main() {
int a, b, c;
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> a >> b >> c;
cout << solve(a, b, c);
return 0;
}
728x90
반응형
'💡 Problem Solving > Baekjoon' 카테고리의 다른 글
[백준 - 1197] 최소 스패닝 트리 [C++] (0) | 2023.10.20 |
---|---|
[백준 - 7490] 0 만들기 [C++] (0) | 2023.10.19 |
[백준 - 11286] 절댓값 힙 [C++] (0) | 2023.10.18 |
[백준 - 1931] 회의실 배정 [C++] (0) | 2023.10.17 |
[백준 - 1541] 잃어버린 괄호 [C++] (0) | 2023.10.16 |