22.01.17 - [BOJ] 1629. 곱셈

[suhyunsim]

문제

• 곱셈

핵심 아이디어

• 시간초과를 해결하기 위해 두 가지 공식을 적용

1. 거듭제곱
   1-1. 지수(n)가 짝수일 때: a ^ n == (a ^ (n/2)) ^ 2
   1-2. 지수(n)가 홀수일 때: a ^ n == ((a ^ (n/2)) ^ 2) * a
2. (A*B)%C == (A%C * B%C)%C

어려운 점, 실수

• 시간초과를 해결하지 못해서 공식을 검색힘

풀이

package main.java.com.poogle.BOJ.Q1629;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        long b = sc.nextInt();
        long c = sc.nextInt();
        System.out.println(calculate(a, b, c) % c);
    }

    private static long calculate(long a, long b, long c) {
        if (b == 0) return 1;
        else if (b == 1) return a;
        long tmp = calculate(a, b / 2, c) % c;
        if (b % 2 == 0) return (tmp * tmp) % c; //짝수일 때
        else return (((tmp * tmp) % c) * a) % c; //홀수일 때
    }
}