Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

20. 분할 정복

재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.

Java / Python

4. 곱셈

1629번

분할 정복으로 거듭제곱을 빠르게 계산하는 문제

이번 문제는 자연수 A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 문제입니다.

• 이런 방식으로 구현했습니다.

1. b의 값이 짝수인지 홀수인지 파악한다.
2. b = 짝수 : 10^10 -> (10^5)^2 형태
3. b = 홀수 : 10^11 -> (10^5)^2 * 10 형태

• Java

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

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

• Python

import sys
a, b, c = map(int, sys.stdin.readline().split())

def power(a, b, c):
    if b == 1:
        return a % c
    temp = power(a, b//2, c)
    
    if b % 2 == 0:
        return (temp * temp) % c
    else :
        return (temp * temp % c) * a % c		

print(power(a, b, c))