[BOJ 1629] 곱셈 (Java)

문제

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

1629번: 곱셈

 

풀이

아래와 같이 짜면 시간/메모리 초과가 발생한다.

    public static long recur(long a, long b, long c){
        if(a==1 || b==1) return a;
        return a * recur(a, b-1, c) % c;
      }

recur(a*a, b/2, c)로 호출하여 함수 호출 횟수를 줄이는게 핵심이다.

overflow가 발생하지 않도록 여러 곳에 c로 mod연산을 해야한다.

b가 1인 조건일 때 mod연산을 누락해서 한참 헤멨다. (96%에서 틀림 찍힘)

 

소스코드

package divideconquer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1629 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        System.out.println(recur(a, b, c));
    }

    public static long recur(long a, long b, long c){
        if(a==1 || b==1) return a%c;
        a = a%c;
        if(b%2 == 0){
            return recur(a*a%c, b/2, c) % c;
        } else {
            return a * recur(a*a%c, b/2, c) % c;
        }
    }
}