https://www.acmicpc.net/problem/1629
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
단순히 계속 곱했다가는 오버플로우되는 문제. 하지만 모듈러 연산을 적용한다고 해도, 일반적인 반복문으로 접근한다면 시간제한에 걸린다 O(n)이니까.
결국 이 문제의 핵심은
- 숫자가 오버플로우되지 않도록 모듈러연산을 계속해서 적용한다.
- O(n)으로 접근해서는 안된다.
모듈러 연산은 https://codejin.tistory.com/68를 참조하자.
이를 통해 다 곱하고 나누는 것이 아니라, 나머지를 계속 곱하면서 최종적인 값을 찾아야 한다.
그러면 오버플로우는 해결했고 이제 O(n)보다 더 빠르게 풀려면 어떻게 해야할까?
2^10을 계산한다고 치자. 이를 일반적으로 곱한다고 가정하면 10번의 연산을 수행할 것이다. (10번 곱하니까)
하지만, 2^10을 계속 분할해보자. 2^10을 2^5 * 2^5 이런식으로 말이다.
2^10 = 2^5 * 2^5
2^5 = 2^2 * 2^2 * 2
2^2 = 2^1 * 2^1
2^1 = 2
이렇게 4번의 과정을 통해 2^10을 구할 수 있게 된다. 즉, 분할정복이 이 문제의 두번째 핵심이다. 이 둘을 문제에 적용시키자.
#include <stdio.h>
typedef unsigned long long ull;
int mod;
int sol(int a, int b) { // return a^b mod c
if (b == 0) return 1;
else if (b == 1) return a;
else {
ull ret = sol(a, b/2);
if (b & 1) return (a * ((ret * ret) % mod)) % mod;
else return (ret * ret) % mod;
}
}
int main () {
int a, b;
scanf("%d %d %d", &a, &b, &mod);
printf("%d", sol(a % mod, b));
}
인자를 전달할 때에도 결국 우리는 나머지값이 중요하므로 a가 아닌 a % mod값을 전달하도록 한다.
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 2747번 C언어 풀이 (0) | 2021.12.23 |
---|---|
백준 1003번 C++ 풀이 (0) | 2021.12.22 |
백준 1920번 C, C++ 풀이 (0) | 2021.12.07 |
백준 18870번 C++ 풀이 (0) | 2021.11.29 |
백준 1427번 C / C++ 풀이 (0) | 2021.11.29 |