[백준] no1629: 곱셈

문제

자연수 A, B, C 가 주어진다.
A의 B제곱한 수를 C로 나눈 나머지를 구해라.
단, ABC의 범위는 2147483647 보다 작다 (즉, long의 메모리 범위를 초과하지 않는다.)

문제 링크 : https://www.acmicpc.net/problem/1629

---

원리

그냥 단순 계산하면 메모리가 초과된다.

점화식을 이용해서 풀어야 한다.

1. 지수법칙
a의 n + m 제곱 = (a의 n제곱) * (a의 m제곱)

2. 모듈러 합동공식(점화식)
(a * b) % c = ((a % c) * (b % c)) % c

3. 지수 법칙 중 짝수일 때와 홀수일 때 처리 방식
a의 홀수n 제곱 = (a의 n/2제곱) * (a의 n/2제곱) * a

 

---

풀이방법

1. 위의 1, 3번 방식을 이용해 최종적으로 모든 제곱이 a의 1승이 될 때까지 n을 반으로 나눠준다.
2. 1번으로 나온 공식에 모듈러 합동공식(위의 2번 규칙)을 적용한다.

* 만약 모듈러 합동공식을 쓰지 않으면 중간에 메모리가 초과되어 잘못된 계산 결과가 초래된다.

---

나의 코드

1. BigInteger를 이용한 단순 계산 [메모리 초과]

: BigInteger이기 때문에 2147483647를 초과하여 값의 반전이 일어날 걱정은 없지만, 계산 결과가 커져 메모리 초과가 발생한다.

 

2. 지수법칙과 모듈러 합동공식을 이용한 BigInteger 방식

private static BigInteger C;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    BigInteger A = new BigInteger(st.nextToken());
    BigInteger B = new BigInteger(st.nextToken());
    C = new BigInteger(st.nextToken());

    System.out.println(pow(A, B));
}

private static BigInteger pow(BigInteger A, BigInteger exp) {
    if(exp.equals(BigInteger.valueOf(1))) return A.mod(C); // 지수가 1일 경우

    BigInteger temp = pow(A, exp.divide(BigInteger.valueOf(2)));

    if(exp.mod(BigInteger.valueOf(2)).equals(BigInteger.valueOf(1))) return ((temp.multiply(temp).mod(C)).multiply(A)).mod(C); // 지수가 홀수일 경우

    return (temp.multiply(temp)).mod(C); // 지수가 짝수일 경우
}

---

레퍼런스 코드

1. 지수법칙과 모둘러 합동공식을 이용한 long 방식

private 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 = Long.parseLong(st.nextToken());
    long B = Long.parseLong(st.nextToken());
    C = Long.parseLong(st.nextToken());

    System.out.println(pow(A, B));
}

private static long pow(long A, long exp) {
    if(exp == 1) return A % C; // 지수가 1일 경우

    long temp = pow(A, exp/2);

    if(exp % 2 == 1) return ((temp * temp % C) * A) % C; // 지수가 홀수일 경우

    return (temp * temp) % C; // 지수가 짝수일 경우
}