https://www.acmicpc.net/problem/1629
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
문제 간단 정리
정말 간단하다
a,b,c가 주어짐.
a^b을 구하는 문제임.
단 a^b값이 너무 클 수 있으니 c로 나눈 나머지를 구하면됨.
문제 해결 방법
일단 나머지 정리를 알아야함.
나머지 정리는 그냥 간단하게 그냥 ((a%c) * (b%c) %c) 하고 (a*b)%c 같다.
즉, 이런 문제가 나오면 그냥 나머지 구하고 곱해주고 나머지 구해주면 된다.
제한 시간이 2초이기 때문에 1초에 3~5억번 연산을 한다고 했을 때 문제의 주어진 수가 최대 21억이기 때문에
무작정 하나하나 곱해주게 되면 시간 복잡도가 O(n)이기 때문에 시간 초과가 난다.
그래서 이 문제는 분할 정복(divide and conquer)을 사용해야한다.
원리는 이거다 a^8 = a*a*a*a*a*a*a*a 이면 연산을 8번해야하는데
이걸 ((a^2)^2)^2 으로 바꾸어주면 3번의 연산으로 처리할 수 있게 된다.
그래서 재귀 함수를 이용해서 b/2로 넣어주고 b=0일 때는 1을 리턴해준다.
그리고 임시 변수 temp에 함수 리턴값을 넣어주고 그럼 이 리턴 값이 a^(b/2)가 될것이니
이것을 (a^(b/2))^2 해주는것을 반복해주면 된다.
주의할점은 b/2가 홀수 일 경우 리턴 값을 a하나를 더 곱해주어야한다.
예를 들면 2^5 -> 2^2 * 2^2 * 2 이런식으로 말이다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
using namespace std;
long long mt(long long a, long long b, long long c){
if(b == 0) // a^0 일때
return 1; // 1을 리턴해주고
long long temp = mt(a, b / 2, c); //c^(b/2) 을 구해주고
temp = (temp * temp) % c; // (c^(b/2))^2 꼴로 해줌
if (b % 2 == 0) // b가 짝수일 경우
return temp; // 계산된거 리턴
else // 홀수인 경우는 남은거 하나 곱해주어야함.
return (temp*a)%c;
}
int main(){
long long a, b, c;
cin >> a >> b >> c;
long long result = mt(a, b, c);
cout << result;
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
백준 1043 거짓말 c++ [컴공과고씨] (3) | 2022.11.20 |
---|---|
백준 2407 조합 c++ [컴공과고씨] (0) | 2022.11.15 |
백준 1932 정수 삼각형 c++ [컴공과고씨] (0) | 2022.10.26 |
백준 5639 이진 검색 트리(linked list 활용) c++ [컴공과고씨] (0) | 2022.10.22 |
백준 9935 문자열 폭발 c++ [컴공과고씨] (2) | 2022.10.10 |