Java

[백준 1629] 곱셈 (JAVA)

iheeeee6-6 2023. 3. 12. 13:21
728x90

https://www.acmicpc.net/problem/1629

 

1629번: 곱셈

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

www.acmicpc.net

 

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