BOJ_S1_1629

📁 [S1_1629] 곱셈

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 A = Integer.parseInt(st.nextToken());
		long B = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		System.out.println(pow(A,B));
		
		}
	
	static long pow(long a, long b) {
		if(b==1) {
			return a % C;
		}
		
		// 지수를 1/2 한 값을 구해주기 -> 지수 법칙 a^b = a^b/2 * a^b/2
		long temp = pow(a, b/2);
		
		// 지수가 홀수 일 경우
		// 모듈러 법칙 (a * b) % c = ((a%c) * (b%c))%c
		if(b % 2 == 1) {
			return (temp * temp % C) * a % C ;
		}
		
		// 짝수 인 경우
		return temp * temp % C;
		
	}
	
}

🤔 나의 생각

문제만 보면 간단한 문제지만 수의 범위와 시간복잡도를 생각하면 그렇게 간단한 문제는 아니였던 것 같다.
간단히 생각하면 B제곱해서 C로 나눠주는 나머진데 시간이 0.5초기 때문에 A,B,C의 범위를 봐서는 불가능하다.
그래서 생각해 내야하는 방법은 지수 법칙과 모듈러 법칙이다.
먼저 지수 법칙은 2의 4승은 2의 2승 곱하기 2의 2승으로 나눠진다는 거고,
모듈러 연산은 (a * b) % c = ((a%c) * (b%c))%c 이 공식이 성립한다는 것이다.
그래서 먼저 pow 라는 메서드에 지수가 1인 경우에는 그냥 A에서 C를 나눈 나머지를 리턴해주고
지수가 홀수 인 경우에는 지수 법칙을 시행한 수끼리 곱해주고 마지막에 원래 값을 한번더 곱해주는 것이다. 그리고 거기에 모듈러 연산을 이용해 값을 구했다.
마지막 짝수 인 경우에는 지수법칙에 모듈려 연산을 시행하여 값을 구해주었다.
나도 지수 법칙과 모듈러 연산을 떠올리지 못해 찾아보다가 알게된 것인데 참.. 수학공식도 많이 알고 있어야 도움이 될 것 같다..ㅠ