[BOJ 1629] 곱셈 (Java)

BOJ 1629 곱셈

문제풀이

나에겐 너무나도 어려운 수학 문제... 그냥 외우자!

제곱의 성질을 이용하여 분할정복으로 제곱 연산을 O(logn)에 처리하는 알고리즘이다.

10^11 = 10^5 * 10^5 * 10
10^5 = 10^2 * 10^2 * 10
10^2 = 10^1 * 10^1

위와 같이 제곱수가

• 짝수일 때는 밑^제곱수/2 * 밑^제곱수/2 의 형태를
• 홀수일 때는 밑^제곱수/2 * 밑^제곱수/2 * 밑 의 형태를

띄게된다.

구현코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();
		
		System.out.println(power(A % C, B, C));
	}

	private static long power(long a, long b, long c) {
		// b가 1일 때
		if(b == 1) return a;
		
		long temp = power(a, b / 2, c) % c;
		
		// b가 짝수일 때 
		if(b % 2 == 0) {
			return (temp * temp) % c;
		// b가 홀수일 때 
		} else {
			return (((temp * temp) % c) * a) % c;
		}
	}
}