[BOJ] 1629. 곱셈 - JAVA

🔗 문제

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

1629번: 곱셈

 

💻 풀이 및 코드

문제 유형 : 분할정복을 이용한 거듭제곱

 

A 를 B 번 곱한 값을 M 으로 나눈 값을 출력하라.

 

풀이

이곳에서 설명을 아주 잘 해놨다.

https://st-lab.tistory.com/237

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

 

느낀 점

 

 

전체 코드

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

public class Main_bj_1629_곱셈 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_1629.txt"));
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		
		System.out.println(func(A, B, C));
		sc.close();
	}
	
	static long func(int A, int B, int C) {
		if(B==1) {
			return A%C;
		}
		
		long res = func(A, B/2, C);
		res = res*res%C;
		
		if(B%2==0) {
			return res;
		}else {
			return res*A%C;
		}
	}

}