백준 1629 자바 - 곱셈

// 곱셈
package Silver_I_1;

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

public class Ex1629 {

    static long c;

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

        long a = Long.parseLong(st.nextToken()); // 자연수
        long b = Long.parseLong(st.nextToken()); // 지수
        c = Long.parseLong(st.nextToken()); // 나누는 수

        System.out.println(pow(a, b));
    }

    static long pow(long a, long exponent) {
        if (exponent == 1) { // 지수가 1일떄
            return a % c;
        }
        long temp = pow(a, exponent / 2);

        if (exponent % 2 == 1) { // 지수가 홀수일떄
            return (temp * temp % c) * a % c;
        }
        return temp * temp % c; // 지수가 짝수일때
    }
}

 

아래 블로그를 보고 풀었다.

[백준] 1629번 : 곱셈 - JAVA [자바] (tistory.com)

[백준] 1629번 : 곱셈 - JAVA [자바]

 

제곱이 클때 저렇게 풀면 빠르게 풀수 있다는걸 알았다. 모듈러에 대해서도 알았다.

이것을 이용해서 다음엔 행렬 제곱 문제를 풀어봐야겠다.

10830번: 행렬 제곱 (acmicpc.net)