728x90
https://www.acmicpc.net/problem/1629
Math.pow로 하면 시간초과가 발생한다...
분할 정복을 이용하여 문제를 해결할 수 있다!
예를 들어,
다섯제곱수이면
5 -> 2 *2 *1 ->1*1*1*1*1 이다!
네제곱수이면
4->2*2->1*1*1*1이다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static long c;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
long n= Integer.parseInt(st.nextToken());
long b= Integer.parseInt(st.nextToken());
c= Integer.parseInt(st.nextToken());
System.out.println(pow(n,b));
}
static public long pow(long n,long b) {
if(b==1) {
return n%c;
}
long temp= pow(n,b/2);
if(b%2==1) {
return temp*temp%c*n%c;
}
else {
return temp*temp%c;
}
}
}
'Java' 카테고리의 다른 글
[백준 14889] 스타트와 링크 (JAVA) (0) | 2023.03.20 |
---|---|
[백준 1406] 에디터 (JAVA) (0) | 2023.03.19 |
[백준 2740] 행렬 곱셈 (JAVA) (0) | 2023.03.12 |
[백준 10830] 행렬 제곱(JAVA) (0) | 2023.03.12 |
[백준 1474] 밑 줄 (JAVA) (0) | 2023.03.09 |