[백준] 1629번(Java)

📖 곱셈

[ 문제 ]
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

💡풀이

• 지수 법칙 + 모듈러 성질을 이용한 문제 풀이 방식
• 지수 곱을 부분으로 나누어 나머지를 구한 뒤 이를 곱한 값들의 나머지를 구하는 방식으로도 나머지 구하는게 가능함.
• 쉽게 말해 절반으로 나눈 수들의 나머지를 곱한 값의 나머지를 구하는 방식. 필자가 말로 적어놓고도 이해가 안되니 아래 수식을 참고하면 좋을 것 같다..

모듈러 공식
$(A \times B) \bmod C =((A \bmod C) \times (B \bmod C))\ bmod C$
$(A \times B) \bmod C = ((A \bmod C) \times (B \bmod C)) \bmod C$

• 만일 지수가 홀수일 경우 지수를 반으로 나눈 값으로 곱한 수 두 개와 A 하나를 C로 나눈 나머지를 곱한 전체 값을 C로 나누어 구하면 된다.
• 짝수일 경우 : $A^B \bmod C = ((A^b \bmod C) * (A^b \bmod C))\bmod C$
  * $B = b + b$
• 홀수일 경우 : $A^B \bmod C = (((A^b \bmod C) * (A^b \bmod C))\bmod C * (A \bmod C))\bmod C$
  * $B = b + b + 1$

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int A, B, C;
    public static void main(String[] args) throws IOException {
        // 지수 법칙, 모듈러 성질
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        // 모듈러 성질을 이용하는 문제 -> A^B % C -> (A%C)^B
        long ans = div(A, B, C);
        System.out.println(ans);

    }

    private static long div(int a, int b, int c){
        if(b == 0) return 1 % c;
        if(b == 1) return a % c;
        else {
            long tmp = div(a, b/2, c);
            if(b % 2 == 0) return (tmp * tmp) % c;
            else return (((tmp * tmp) % c) * (a % c)) % c;
        }
    }
}

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