(Java) 나머지(모듈러) 연산 (feat. 백준 1629 곱셈)

나머지(모듈러) 연산

나머지를 구하는 연산으로 예를 들어, 두 정수 A, B에 대해서 A를 B로 나누어서 C가 나왔다면

A % B = C 또는 A mod B = C 이다.

 

나머지(모듈러) 연산에는 덧셈, 뺄셈, 곱셈 성질이 있다.

덧셈 성질	(A+B) mod C = (A mod C + B mod C) mod C
뺄셈 성질	(A-B) mod C = (A mod C - B mod C) mod C
곱셈 성질	(A*B) mod C = ((A mod C) * (B mod C)) mod C

 

 

우리는 이러한 성질을 이용해 int의 범위를 넘어서는 값을 int로 표현할 수 있거나 큰 값을 계산할 경우 분할정복을 통해 간단하게 표현할 수 있다.

 

'백준 1629번 문제 곱셈' 이 이러한 성질을 이용한 문제이다.

 

 

백준 1629 곱셈

https://www.acmicpc.net/problem/1629

A, B, C가 주어지고 A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 문제이다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        /**
         * ((A^2)^2)^2...)이런 식으로 제곱으로 나타내면 제곱 수는 1 2 4 8 ... 이런식으로 상승할텐데
         * 이것은 이진수의 자리수와 동일하다.
         * B를 이진수로 나타낸 뒤 위의 제곱들 중 해당하는 자리수의 경우에만 곱해주면 될 것이다.
         */
        long squareVal = A;  // 현재 제곱하고 있는 중인 값
        long mult = 1;
        while(B != 0) {
            if(B % 2 == 1) {
                mult = (mult*squareVal)%C;
            }
            B = B >> 1;
            squareVal = (squareVal * squareVal)% C;
        }

        System.out.println(mult);
    }
}

 

예시로 주어진 값이

A: 10, B: 11, C: 12 인데 이는 10^11을 12로 나눈것과 같다.

 

B는 이진수로 나타내면 1011이고, 제곱은 10^11 = 10^(1+2+8) = 10^1 * 10^2 * 10^8 이런 식으로 나타낼 수 있다.

그리고 (10^1)^2 = 10^2 이고, (10^4)^2 = 10^8이므로 A로부터 시작해 제곱 계산을 해주며 B의 이진수 자리수가 1인 곳마다 정답 변수에 곱해줬다. 물론 모듈러 연산의 곱셈 성질을 적용해 오버플로우가 일어나지 않도록 했다.

 

 

문제 풀이 중 시행착오

1. 처음에는 모듈러 연산만 적용해주고 단순 반복문으로 구하려고 했다. 시간 초과였다. B번 계산해야하는데 최악의 경우 21억번 계산해야 한다. 연산은 1초에 약 1억개 이루어지므로 계산을 2억개 내로 만들어야 했다. 

 

2. squareVal을 제곱하는 과정에서 Math.pow() 메소드를 사용하려고 했다. 하지만 Math.pow()에는 문제가 있었는데 부동소수점 연산을 사용하여 정확도 문제가 발생할 수 있다는 점이었다. 이를 해결하기 위해 squareVal * squareVal로 직접 곱해줬다.