[SWEA] 13736. 사탕 분배

문제

---

A, B, Sum = A+B 라 하자. 처음에 사탕을 나눌 때 [A, Sum - A] 로 나타낼 수 있다. 이때 대소에 의해 [2A, Sum - 2A], [2A - Sum, 2Sum - 2A] 으로 나타낼 수 있다. 대소관계를 모르지만 두 값에서 2A % Sum == (2A - Sum) % Sum 이므로 첫 번째 사탕을 나누었을 때 어느 한 명이 가진 사탕의 수는 2A % Sum 으로 나타낼 수 있다. 이후 한 번 더 진행하면 4A % Sum % Sum 임을 확인할 수 있으므로 k 번째에서는 2^k * A % Sum 이 한 쪽의 사탕 수라 할 수 있다.

이 때, 시간 초과가 나지 않도록 하기 위해 거듭제곱을 분할 정복으로 나타낼 수 있다.

실수

---

일반항을 생각해내기에 어려워서 혼자 생각해내지는 못했다. 일반항 구하는 새로운 유형을 겪어본 느낌.

mod 를 구할 때 거듭제곱이라면 mod 후 곱해도 된다. (A % B = C -> A = B * Q + C, A^2 = B(…) + C^2)

크기가 큰 만큼 long 타입을 사용했어야했는데, int 해놓고 오답이 나서 시간을 계속 썼다.

코드

---

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class Solution {
    static StringBuilder result = new StringBuilder();

    public static void main(String args[]) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        long A, B, K, Sum;
        //////////////////////////
        ///////////////////////////
        for (int test_case = 1; test_case <= T; test_case++) {
            result.append("#" + test_case + " ");
            st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            /////////////////////////////
            Sum = A + B;
            B = (twoPow(K, Sum) * A) % Sum;
            //////////////////////////////
            result.append(Math.min(B, Sum - B) + "\n");
        }
        System.out.println(result);
    }

    static long twoPow(long n, long sum) {
        if (n == 0)
            return 1;
        if (n == 1)
            return 2;
        long ret;
        if (n % 2 == 0) { // 짝수
            ret = twoPow(n / 2, sum);
            return (ret * ret) % sum;
        } else { // 홀수
            ret = twoPow((n - 1) / 2, sum);
            return (ret * ret * 2) % sum;
        }
    }
}