[백준] 1629번 곱셈 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
20. 분할 정복
재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.
재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.
Java / Python
4. 곱셈
분할 정복으로 거듭제곱을 빠르게 계산하는 문제
이번 문제는 자연수 A를 B번 곱한 수를 C로 나눈 나머지를 출력하는 문제입니다.
- 이런 방식으로 구현했습니다.
- b의 값이 짝수인지 홀수인지 파악한다.
- b = 짝수 : 10^10 -> (10^5)^2 형태
- 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))
Author And Source
이 문제에 관하여([백준] 1629번 곱셈 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-1629번-곱셈-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)