문제

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

풀이

a를 b로 나눈다고 가정
a = b * c + d
a^2 = b * c1 + d1
a^3 = b * c2 + d2

a^2 = a(bc + d) = abc + ad
(a^2 를 b로 나눈 나머지) = (ad를 b로 나눈 나머지)

ex) 8 % 5 = 3
8^2 % 5 = 4
8*3 % 5 = 4

---

a^2 = (bc + d)^2 = (bc)^2 + 2bcd + d^2
(a^2 를 b로 나눈 나머지) = (d^2를 b로 나눈 나머지)

ex) 8 % 5 = 3
8^2 % 5 = 4
3 * 3 % 5 = 4

즉, A를 대신하여 A를 C로 나눈 나머지를 갖고 다녀도 된다는 느낌이다.

위 원리를 이용하여 로직을 작성하였다.

import java.util.Scanner;

public class Num1629 {

    public static int A;
    public static int B;
    public static int C;
    public static long result;
    public static long rest = 1;

    public static void main(String[] args) {
        //input
        Scanner scanner = new Scanner(System.in);
        String[] a = scanner.nextLine().split(" ");
        A = Integer.parseInt(a[0]);
        B = Integer.parseInt(a[1]);
        C = Integer.parseInt(a[2]);

        //logic
        // A^2 % C   =   (A % C) * (A % C) % C
        result = A % C;
        while (B != 1) {
            // 23 % 2 -> 1   (2^2)11 * rest
            if (B % 2 == 1) {
                rest *= result;
                rest %= C;
            }
            B /= 2;

            // (A % C)^2
            result *= result;
            result %= C;
        }
        result *= rest;
        result %= C;

        //output
        System.out.println(result);
    }
}