[백준] 13171. A

문제 링크

[백준] 13171. A

풀이 과정

지수가 $10^{18}$까지 가능하므로, $A^X$는 long으로 표현하지 못합니다.

예를 들어, $2^{10}$은 $2^{10}=2^{8+2}=2^8\cdot2^2$으로 표현됩니다. 즉, 지수를 2진수로 표현할 수 있고, 이를 연산에 적용할 수 있습니다.

A는 2진수로 표현된 X의 자리가 증가할 수록, 그 값을 제곱한 값으로 변경됩니다. 이를 통해 각 자리가 1010(2)의 우측부터 2, 4, 16, 256의 값을 가리키게 됩니다.

비트가 1로 켜져있다면, answer에 A를 곱함으로써 중간 값을 누적해 나갈 수 있습니다.

while (X > 0) {
    if ((X & 1) == 1)
        answer = answer * A % MOD;

    X >>= 1;
    A = A * A % MOD;
}

위 그림에서 봤던 과정을 코드로 작성한 것입니다. X를 2진수로 표현해, 제일 우측 비트가 1인 경우에는 누적된 값 A를 곱해줍니다. 이후, X는 우측으로 시프트시키고, A는 제곱시켜 줍니다. 이 과정을 X가 0이 될 때까지 반복합니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Long A = sc.nextLong();
        Long X = sc.nextLong();
        final int MOD = 1_000_000_007;
        Long answer = 1L;
        A %= MOD;

        while (X > 0) {
            if ((X & 1) == 1)
                answer = answer * A % MOD;

            X >>= 1;
            A = A * A % MOD;
        }

        System.out.println(answer);
    }
}