167. 1629(곱셈) - 자바

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

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, B, C));

	}

	private static long power(long A, long B, long C) {
		if (B == 0) {
			return 1;
		}

		long tmp = power(A, B / 2, C);

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

문제요약

A,B,C가 주어지는데 A를 B번 곱한 값을 C로 나누어라 (A,B,C <= 2,147,483,647)

설명

수가 매우매우 크기 때문에 온전히 A를 B번 곱하면 시간초과가 발생할 수 밖에 없다.

따라서 분할정복을 사용하면 된다.

 

제곱에는 특징이 있다.

다음과 같이 11승을 단 3번만으로 연산을 끝낼 수 있다. O(log N)

 

단, 두가지 경우를 생각해야한다.

1. 지수가 짝수일 때

예를 들어  2^10인 경우 2^5 * 2^5로 나타낼 수 있다.

N^(k/2) * N^(k/2)

 

2. 지수가 홀수일 때

예를 들어 2^11인 경우 2^5 * 2^5 * 2 로 나타낼 수 있다.

N^((k-1)/2) * N^((k-1)/2) * N

 

		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();

먼저 A,B,C를 받는다.

 

	private static long power(long A, long B, long C) {
		if (B == 0) {
			return 1;
		}

		long tmp = power(A, B / 2, C);

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

만약 지수가 0이면 1을 반환하면 된다.

 

tmp에 지수를 반으로 나눈 값을 넣어 재귀함수를 호출한다.

 

만약 지수가 홀수이면 (tmp * tmp % C) * A % C 식으로 나타내고,

 

지수가 짝수이면 (tmp * tmp) % C 식을 나타낸다.

 

홀수에서 C를 먼저 나눠준 이유는 수가 long을 넘어가는 것을 방지하기 위함이다.