[백준] 1629번: 곱셈

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;
}

'알고리즘' 카테고리의 다른 글