문제 설명

A, B, C 가 주어진다. A를 B번 곱한 것을 C로 나눈 나머지를 구하라.

문제 제약

A, B, C는 21억 이하의 자연수이며, 시간제한은 0.5초다.

접근

일다 보자마자 모듈로 연산의 분배법칙이 떠올랐다.
하지만, 이걸 B번 반복하는것은 21억번이라서 너무컸고, 묶음단위로 A를 여러개 곱한 값을 C로 나눈값의 나머지를 활용해서 모듈러 연산 분배법칙을 적용하고자 했다.
그렇다면 어떻게 해야 효율적으로 묶음 단위를 찾을 수 있을까 생각했다.
(A A A A A A A A A A...A) % C

우선, 묶음 단위에 대한 나머지값을 저장하기 위해 dp라는 이름의 배열을 쓴다면 다음과 같이 써야할 것이다. 하지만, 아래처럼 하면 B는 최대 21억이므로 시간초과가 뻔하다.
dp[1] = A를 1번 곱하고 C로 나눈 나머지
dp[2] = A를 2번 곱하고 C로 나눈 나머지
dp[3] = A를 3번 곱하고 C로 나눈 나머지
dp[4] = A를 4번 곱하고 C로 나눈 나머지
...
dp[B] = A를 B번 곱하고 C로 나눈 나머지

하지만, 생각해보면 굳이 다 구할 이유가 없다. 우리는 적절한 묶음 단위를 찾는게 핵심이기 때문이다.
피보나치를 활용해서 중간중간 건너뛰면서 B의 절반까지만 dp를 구해놓으면 된다.

dp[1] = A를 1번 곱하고 C로 나눈 나머지
dp[2] = A를 2번 곱하고 C로 나눈 나머지
dp[3] = A를 3번 곱하고 C로 나눈 나머지 == dp[1] * dp[2] % C
dp[5] = A를 5번 곱하고 C로 나눈 나머지 == dp[2] * dp[3] % C
dp[8] = A를 8번 곱하고 C로 나눈 나머지 == dp[3] * dp[5] % C
...
dp[B/2] = A를 B/2번 곱하고 C로 나눈 나머지 == dp[B/2-1] * dp[B/2-2] % C

이렇게 건너뜀면서 묶음 단위를 구해놨으면, 내가 과거에 구해놨던 것들 중 아직 곱하지 않은 갯수와 가장 가까운 것을 활용하면 된다.
이를 위해 피노나치 수열 개념을 활용해서 어딘가에 저 값을 저장해야하는데, 인덱스로 추적하기에는 무리가 있다고 판단해서 ArrayList를 두 개 선언했다.
size는 1,2,3,5,8,12,...B/2 들을 저장할 리스트고,
dp는 A를 1번 곱하고 C로 나눈 나머지, A를 2번 곱하고 C로 나눈 나머지, ... 이녀석들을 저장할 리스트다.

이제 while문을 돌며 우리가 구해놔서 저장했던 값들을 활용해서 remainB라는 변수를 줄여나가면 된다.

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

public class Main {
    static int A, B, C;
    static int HALF_B;
    static ArrayList<Integer> size = new ArrayList<>();
    static ArrayList<Long> dp = new ArrayList<>();

    static void calculateFibonacciDp() {
        if (size.get(size.size() - 1) > HALF_B) return;
        size.add(size.get(size.size() - 2) + size.get(size.size() - 1));
        dp.add(dp.get(dp.size() - 2) * dp.get(dp.size() - 1) % C);
        calculateFibonacciDp();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        HALF_B = B / 2;
        size.add(1);
        dp.add((long) A % C);
        size.add(2);
        dp.add(dp.get(0) * dp.get(0) % C);
        calculateFibonacciDp();

        int remainSize = B;
        long result = 1;
        int curUnitSzie = size.get(size.size() - 1);
        long curUnitDp = dp.get(dp.size() - 1);
        int curIndex = dp.size() - 1;
        while (true) {
            if (curUnitSzie > remainSize) {
                curIndex--;
                curUnitSzie = size.get(curIndex);
                curUnitDp = dp.get(curIndex);
                continue;
            }

            result = (curUnitDp * result) % C;
            remainSize -= curUnitSzie;
            if (remainSize == 0) break;
        }

        System.out.println(result);
    }
}

느낀점

처음엔 실버문제인걸 보고 그냥 모듈러 연산 분배법칙 쓰고 끝내려다가 시간 조건을 다시보고 당황했다. 적절한 묶음단위를 찾으려고 dp를 사용했고, dp를 효율적으로 저장하기 위해 피보나치까지 왔다. 개인적으로는 이게 왜 실버 문제인지 모를 정도로 난이도가 있게 느껴졌다.