[백준/Silver I] 곱셈 - 1629

[Silver I] 곱셈 - 1629

문제 링크

성능 요약

메모리: 11512 KB, 시간: 68 ms

분류

분할 정복을 이용한 거듭제곱, 수학

제출 일자

2024년 11월 20일 05:17:50

문제 설명

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

 

제출 코드

이 문제는 A, B, C의 숫자가 굉장히 클 수 있다는 점을 고려해야한다.
시간제한은 0.5초인데 for문을 그냥 사용하면 최악의 경우 2,147,483,647번 돌아야 하므로 시간초과가 발생할 수 있다.
때문에 분할정복으로 문제를 해결해야 한다.

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

import java.io.*;
import java.util.*;

public class Main {

    static long sqrt(long a, long b, long c){
        if(b==1) return a%c; // b가 1이면 a%c를 반환
        long temp = sqrt(a, b/2, c); // b를 2로 나누어 재귀호출
        if(b%2 == 0){ // b가 짝수이면 재귀호출 결과를 제곱하고 c로 나눈 나머지 반환
            return temp*temp % c;
        }else{ // b가 홀수이면 재귀호출 결과를 제곱하고 a를 한번 더 곱해준 후 c로 나눈 나머지 반환
            return ((temp*temp % c) *a) % c;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // a, b, c 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Integer.parseInt(st.nextToken());
        long b = Integer.parseInt(st.nextToken());
        long c = Integer.parseInt(st.nextToken());
        br.close();

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


}