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

곱셈

풀이

a,b,c가 주어지면 a를 b번 곱하여 c로 나눈 나머지를 구하는 문제다.

여기서 수의 범위가 Integer의 최대값과 같기때문에 선언을 int가 아니라 long으로 해야한다.(java 기준)

또한 일반적인 재귀로 거듭제곱을 구현할 경우 '메모리 초과'라는 결과를 얻을 것이다.

따라서 곱하는 회수인 b를 계속 2로 나누어 b가 1이 될 때까지 재귀함수를 호출한다.

이후 중요한 것은 b가 홀수일 때랑 짝수일 때랑 경우가 다르다는 것이다.

2^11을 생각하면 2^5 2^5 2이기 때문에 홀수일 경우 return 하기 전에 a를 한번 곱해줘야한다. 짝수와는 달리

따라서

if (b % 2 == 0) {
	return temp * temp;
}
else {
	return (temp * temp) * a;
}

와 같다.

또한 곱하는 과정에서 long의 범위를 벗어나는 경우도 있다. 그것을 방지하기 위해 c로 나눈 나머지를 구하는 것인데 모듈러 연산의 성질에 대해 알아두면 좋다.

(AB)%C = (A % C) (B % C) % C

와 같다.

따라서 재귀함수의 리턴을 c로 나눈 나머지로 해줘야한다.

최종적으로

if (b % 2 == 0) {
	return temp * temp % c;
}
else {
	return (temp * temp) %c * a % c;
}

가 된다.

중요한 것은 재귀 호출을 최적화하는 것과 계산한 결과가 자료형 범위를 벗어나지 않도록 하는 것이다.

코드

import java.io.*;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first = br.readLine().split(" ");
        long a = Long.parseLong(first[0]);
        long b = Long.parseLong(first[1]);
        long c = Long.parseLong(first[2]);

        bw.write(mul(a,b,c)+"\n");

        br.close();
        bw.close();
    }

    private static long mul(long a, long b, long c) {
        if (b == 1)
            return a % c;
        long temp = mul(a, b/2, c);
        if (b % 2 == 0) {
            return temp * temp % c;
        }
        else {
            return (temp * temp) % c * a % c;
        }
    }
}