11778 : 피보나치 수와 최대공약수 - JAVA

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

11778번: 피보나치 수와 최대공약수

피보나치수 두개의 최대공약수를 구하는 문제이다.

해당 순서의 피보나치 수를 구하고 gcd(최대공약수)를 통하여 피보나치수를 구하는것과 최대공약수를 구하고 gcd를 구하는것은 같다고 한다.

 

나는 처음에는 피보나치 수 두가지를 모두 구하고, gcd를 구했는데, 제시된 테스트케이스는 통과하였지만, 어쨌든 분할 정복은 두번 돌아가기에, 값이 큰 경우 지정 시간 내에 못도는 문제가 있었다. 따라서 시간초과를 받았고, 힌트에서 fiboanacci(gcd(n,m)) = gcd(fibonacci(n), fibonacci(m))가 있어서 최대공약수를 구하고 피보나치수열을 구했고, 통과했다.

 

만약 전자대로 할 경우 gcd가 너무 많이 돌고 그 뒤 분할정복이 도는 방식이라 시간 초과가 난다.

 

피보나치 수의 분할정복은 다음과 같은 아이디어를 이용하였다.

이것이 피보나치 수열의 일반화인 F(n) = F(n-1) + F(n-2)와 같다.

이 형태의 행렬이 있다고 가정한다. {{0,1}, {1,1}}

이 행렬을 한번 곱한다. {{1,1}, {1,2}}가 나온다.

그렇게 나온 행렬끼리 또 곱한다. {{2, 3}, {3, 5}}가 나온다.

[0][1]과 [1][0]은 F(n)이고, 여기서는 [1][1]은 F(n+1)이다. 

따라서 행렬간 1, 1, 2, 3, 5 ..의 피보나치 수열이 도출된다.

 

이 원리와 분할정복을 이용하여 다양한 문제들도 풀 수 있다.

이것 외에도 피보나치 수로 시작하는 골드 상위권 문제는, 피사노정리를 이용하거나, 분할정복 + 행렬 거듭 제곱을 이용하는 문제이기 때문이다.

 

나는 앞서 설명한 원리와 분할정복을 이용하여 풀었다.

아래 나온 matPow함수로 분할정복을 구현했고, 이문제에서는 {{1,1}{1,0}}으로 진행했다. 답에는 변화가 없다.

 

//gcd 구한뒤 피보나치 수 구하는걸 요구하고 있는것
import java.util.*;
import java.io.*;
public class Main {
	static final long mod = 1000000007;
	public static long[][] fibo = {{1, 1}, {1, 0}};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Long.parseLong(st.nextToken());
		long m = Long.parseLong(st.nextToken());
		long[][] res;
		long gcd = 0;
		if(n < m) {
			gcd =gcd(m,n);
		}
		else {
			gcd = gcd(n,m);
		}
		res = matPow(fibo, gcd);
		System.out.println(res[1][0]);
	}

	public static long gcd(long a, long b){
		long n;
		while(b != 0) {
			n = a%b;
			a = b;
			b = n;
		}
		return a;
	}
    public static long[][] matPow(long[][] tmp, long exp) {
        if(exp == 1) {
            return tmp;
        } else if(exp == 0) {
            long[][] zero = {{0, 0},{0, 0}};
            return zero;
        }

        long[][] res = matPow(tmp, exp / 2);
        long[][] f = {{1, 0}, {0,1}};
        if(exp % 2 == 1) {
            return matMul(matMul(res, res), tmp);
        } else {
            return matMul(res, res);
        }
    }
    public static long[][] matMul(long[][] tmp1, long[][] tmp2) {
        long[][] res = new long[2][2];

        res[0][0] = ( (tmp1[0][0] * tmp2[0][0]) + (tmp1[0][1] * tmp2[1][0])) %mod;
        res[0][1] = ( (tmp1[0][0] * tmp2[0][1]) + (tmp1[0][1] * tmp2[1][1])) %mod;
        res[1][0] = ( (tmp1[1][0] * tmp2[0][0]) + (tmp1[1][1] * tmp2[1][0])) %mod;
        res[1][1] = ( (tmp1[1][0] * tmp2[0][1]) + (tmp1[1][1] * tmp2[1][1])) %mod;

        return res;
    }

}

 

 

같은 풀이방식을 사용하는 문제는 이것이 있다.

역시 피보나치수열의 최대공약수를 사용한다.

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

11238번: Fibo