백준 1629 곱셈 (java)

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

모듈로 분배법칙과 거듭제곱 분할정복을 함께 사용해야 하는 문제.

10을 11번 곱하면 곱하기를 11번 해야 하지만. 분할정복을 통해 해결하면 log2(11)번으로 해결할 수 있다.

 

재귀 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.*;

public class Main {
    static long a,b,c;
    static long result=0;
    static long solve(long num){
        if(num<=1) return a %c;
        long temp = solve(num/2);
        if(num%2==0){
            return temp * temp % c;
        }
        else{
            return temp * temp % c * a % c;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        StringTokenizer token = new StringTokenizer(str);
        a=Long.parseLong(token.nextToken()); b=Long.parseLong(token.nextToken()); c=Long.parseLong(token.nextToken());

        bw.write(solve(b)+"");
        bw.flush();
        bw.close();
    }
}

2로 나누게 되면, 홀수일 때 나머지를 버리기 때문에

거듭제곱해야 하는 남은 수가 홀수면 /2번 거듭제곱한 수를 제곱하고 버린 나머지분량을 채우기 위해 a만큼 곱해준다.

곱했을 때 매우 큰 수가 될 수 있으므로 모듈로 분배법칙을 이용해서 매번 나머지 연산을 적용해준다.

짝수번 남았을 때는 버림되는 수가 없기에 그냥 해주면 된다.

 

반복문 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.*;

public class Main {
    static long a,b,c;
    static long result=0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        StringTokenizer token = new StringTokenizer(str);
        a=Long.parseLong(token.nextToken()); b=Long.parseLong(token.nextToken()); c=Long.parseLong(token.nextToken());
        long result = 1;
        while(b>0){
            if(b%2==1){
                result= result * a % c;
                b--;
            }
            a=a*a%c;
            b/=2;
        }

        bw.write(result+"");
        bw.flush();
        bw.close();
    }
}