[Silver I] 곱셈 - 1629
성능 요약
메모리: 12856 KB, 시간: 112 ms
분류
분할 정복을 이용한 거듭제곱, 수학
제출 일자
2023년 11월 16일 10:58:00
문제 설명
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
long c = Long.parseLong(st.nextToken());
System.out.println(POW(a,b,c));
}
private static long POW(long base, long exponent, long mod){
if(exponent == 1){
return base % mod;
}
long tmp = POW(base,exponent / 2, mod);
// 홀수일 때 ex) 2^5 -> 2 * 2^2 * 2^2
if(exponent % 2 == 1){
return (tmp * tmp % mod) * base % mod;
}
// 짝수일 때 ex) 2^8 -> 2^4 * 2^4
else{
return tmp * tmp % mod;
}
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 11723번 : 집합 Silver5(실버5) - JAVA[자바] (0) | 2023.11.17 |
---|---|
[백준] 16948번 : 데스 나이트 Silver1(실버1) - JAVA[자바] (0) | 2023.11.17 |
[백준] 11051번 : 이항 계수2 Silver2(실버2) - JAVA[자바] (0) | 2023.11.08 |
[백준] 1747번 : 소수&팰린드롬 Silver1(실버1) - JAVA[자바] (0) | 2023.11.01 |
[백준] 12026번 : BOJ 거리 Silver1(실버1) - JAVA[자바] (0) | 2023.10.26 |