[백준] 1629 - 곱셈 (Java)

[백준] 1629 - 곱셈 (Java)

문제

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

1629번: 곱셈

풀이/후기

수상할정도로 단순한 문제처럼 보이지만, 생각할 것이 많은 문제였다.

당연히 입력받은 값끼리 제곱하여 나머지 구하는 문제는 틀렸다고 채점된다.

long 자료형 하나로 풀기는 가능하지만,

제곱을 하게되면 그 이상이 나오기 때문에 결과값이 달라 틀렸다고 채점되는것이다.

이 문제는 모르는 것을 인정하고 바로 검색을 하게됐는데,

- 지수법칙

- 모듈러 합동 공식

이 두가지를 이용하면 간단하게 풀 수 있다.

두가지 방법과 예시는 소스코드에 같이 적어두었는데,

참고에 적어둔 블로그에서 모듈러 공식을 아주 잘 정리해주셔서 이해가 잘 됐다 ㅎㅎ

코드

package DivideAndConquer;

import java.io.*;
import java.util.*;

public class Problem1629 {
	
	static long C;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		
		long A = Long.parseLong(str.nextToken());
		long B = Long.parseLong(str.nextToken());
		C = Long.parseLong(str.nextToken());
		
		
		/*
		(A ^ B) % C
		(A * A) % C
		=> ((A % C) * (A % C)) % C
		 * 
		 */
		
		
		//System.out.println( Math.pow(A, B) % C);
		System.out.println(powFunc(A, B));
	}
	
	static long powFunc(long A, long B) {
		
		if (B == 1) {
			return A % C;
		}
		
		/* 지수의 법칙 사용
		 * A^(N+M) = A^N * A*M
		 * A^8 	= (A^4) * (A^4)
		 * 		= (A^2) * (A^2) * (A^2) * (A^2)
		 * 		= ((A^1) * (A^1)) * ((A^1) * (A^1)) * ((A^1) * (A^1)) * ((A^1) * (A^1))
		 */
		long temp = powFunc(A, B / 2);
		
		//지수가 홀수인 경우 		(A^B/2) * (A^B/2) * A
		/*	모듈러 합동 공식 사용
		 * (temp * temp * A) % C 
		 * 			= (( temp * temp % C) * (A % C)) % C
					= (((temp * temp % C) % C) * (A % C)) % C 	// (temp * temp % C) = (temp * temp % C) % C
					= (( temp * temp % C) * A) % C
		 */
		if (B % 2 == 1) return (temp * temp % C) * A % C;
		
		return temp * temp %  C;
	}

}

 

Commit

커밋했는데 깃에서 안뜨는즁,,,ㅠㅠ

Can't connect to any repository: https://github.com/allrightDJ0108/CodingTestStudy.git (Nothing to push.)

참고

https://st-lab.tistory.com/237

[백준] 1629번 : 곱셈 - JAVA [자바]