#백준_1629 곱셈 - Java 자바

#유형 : 수학, 분할 정복, 재귀

#난이도 : 실버 1

# A,B,C의 값이  2,147,483,647 이하이기 때문에, 단순하게 for문을 돌리면 시간복잡도가 너무 답이 없다. 

여기서 분할 정복의 바탕인 재귀를 사용한다면 어떻게 될까?

2^31이 약 2,147,483,647 이기 때문에, 2,147,483,647 번 돌리는 반복문 댓긴 재귀 방식을 활용하면 31번의 연산으로 퉁칠수 있다. 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1629 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        long A,B,C;
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Long.parseLong(st.nextToken());
        B = Long.parseLong(st.nextToken());
        C = Long.parseLong(st.nextToken());
        
        System.out.println(solve(A%C, B, C));
    }
    
    public static long solve(long a, long b, long c) {
        if(b == 1)
            return a;
        else {
            long next = solve(a, b/2, c);
            if(b%2 == 1) {
                return ((next * next) % c * a) % c;
            }else
                return (next*next)%c;
        }
    }
}