2019. 7. 26. 18:29ㆍ알고리즘
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
예제 입력 1
10 11 12
예제 출력 1
4
B의 범위가 굉장히 큰 것을 알 수 있죠. 이걸 반복문으로 처리하려고 하면 시간 초과가 날 수 있습니다.
n제곱을 해결하는 방법은 분할 정복으로 해결할 수 있습니다.
a^b = a^(b / 2) * a^(b / 2) 인 것을 이용해서 문제를 풀 수 있습니다.
만약 b가 홀수라면, a^b = a^(b / 2) * a^(b / 2) * a 이겠죠?
예외 처리에 신경 써서 문제를 풀어주면 됩니다.
mod 연산은 곱셈에 대해서 분배 법칙이 성립합니다.
(a * b) % c = ((a % c) * (b % c)) % c
a = ck1 + r1
b = ck2 + r2
라고 한다면, a * b = c^2 * k1 * k2 + ck1r2 + ck2r1 + r1r2 가 될 것이고, 이에 mod c를 해주면 r1r2만 남습니다.
이 r1 = a % c, r2 = b % c이므로 성립한다고 볼 수 있습니다.
그렇기 때문에 단계별로 계속 mod 연산을 해주면 문제를 풀 수 있습니다.
#include <iostream>
using namespace std;
long long a, b, c;
long long calc(int i) {
if (i == 0) return 1;
long long tmp = calc(i / 2);
long long result = (tmp * tmp) % c;
if (i % 2 == 1) return (result * a) % c;
return result;
}
int main() {
cin >> a >> b >> c;
cout << calc(b) << '\n';
return 0;
}
'알고리즘' 카테고리의 다른 글
[백준] 10830번: 행렬 제곱 (0) | 2019.07.26 |
---|---|
[백준] 1016번: 제곱 ㄴㄴ 수 (0) | 2019.07.26 |
[백준] 1495번: 기타리스트 (0) | 2019.07.12 |
[백준] 1720번: 타일 코드 (0) | 2019.07.12 |
[백준] 1328번: 고층 빌딩 (0) | 2019.07.03 |