[BaekJoon] 11778 피보나치 수와 최대공약수 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final long DIVISOR = 1_000_000_007;
    static long n, m;

    static void input() {
        Reader scanner = new Reader();

        n = scanner.nextLong();
        m = scanner.nextLong();
    }

    static void solution() {
        // 피보나치의 성질 중에는 다음과 같은 성질이 존재한다
        //  -> gcd(fibo(a), fibo(b)) = fibo(gcd(a, b))
        // 그러므로 주어진 n, m에 대해 먼저 유클리드 호제법을 통해 최대공약수를 구한다
        // 그 이후, 해당 수에 맞는 피보나치 수를 구한다
        long gcd = getGCD(Math.max(n, m), Math.min(n, m));
        long[][] fibo = getFiboNum(gcd - 1, new long[][] {{1L, 1L}, {1L, 0L}});
        System.out.println(fibo[0][0] % DIVISOR);
    }

    static long getGCD(long n1, long n2) {
        if(n2 == 0) return n1;
        return getGCD(n2, n1 % n2);
    }

    static long[][] getFiboNum(long num, long[][] mat) {
        if(num == 0 || num == 1) return mat;

        long[][] result = getFiboNum(num / 2, mat);
        result = multiplyMat(result, result);

        if(num % 2 == 1L) result = multiplyMat(result, mat);

        return result;
    }

    static long[][] multiplyMat(long[][] mat1, long[][] mat2) {
        long[][] result = new long[2][2];

        result[0][0] = (mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0]) % DIVISOR;
        result[0][1] = (mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1]) % DIVISOR;
        result[1][0] = (mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0]) % DIVISOR;
        result[1][1] = (mat1[1][0] * mat2[1][0] + mat1[1][1] * mat2[1][1]) % DIVISOR;

        return result;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        Long nextLong() {
            return Long.parseLong(next());
        }
    }
}