문제 출처

단계별로 풀어보기 > 분할 정복 > 곱셈
https://www.acmicpc.net/problem/1629

문제 설명

자연수 A를 B번 곱한 수를 C로 나눈 나머지를 출력하라.

접근 방법

지수법칙과 모듈러 공식를 이용하여 풀이한다.

// 지수법칙 예시
a^5 = a^2 x a^3

// 모듈러 공식 예시
(a * b) % C
= (a % C ) * (b % C)

재귀를 이용하여 B를 절반씩 쪼개준다. 그렇게, 1이 되면 A % C를 return하고, 그 값을 통해 서로 곱한 값을 다시 return한다.

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

public class 곱셈 {

    public static long C;

    public static long pow(long A, long exponent){

        if(exponent == 1){
            return A % C;
        }

        long tmp = pow(A, exponent / 2);

        if(exponent % 2 == 1){
            return (tmp % C * tmp % C) * A % C;
        }
        return tmp % C * tmp % C;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        bw.write(String.valueOf(pow(A, B)));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

        if(exponent % 2 == 1){
            return (tmp % C * tmp % C) * A % C;
        }
        return tmp % C * tmp % C;
    }

해당 부분은

        if(exponent % 2 == 1){
            return (tmp * tmp % C) * A % C;
        }
        return tmp * tmp % C;
    }

와 같은 형태로 바꿀 수 있다.(풀이에 문제 없고, 효율성 부분에도 필요없는 계산을 하지 않으므로 더 좋다.)

시간 복잡도는 O(log B)의 시간 복잡도를 가진다.

문제푼 흔적