[2749번] 피보나치 수 3

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 피사노 주기(Pisano Period) :: https://www.google.co.kr/search?q=%ED%94%BC%EC%82%AC%EB%85%B8+%EC%A3%BC%EA%B8%B0(Pisano+Period)&oq=%ED%94%BC%EC%82%AC%EB%85%B8+%EC%A3%BC%EA%B8%B0(Pisano+Period)&aqs=chrome..69i57j69i60.143j0j4&sourceid=chrome&ie=UTF-8

피사노 주기라는 개념을 이용하여 풀면 된다.

나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10임을 알 수 있다.

 

몇가지 성질들은 아래와 같다.

 

m > 2인 경우에 k(m)은 짝수이다.

임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.

k(m) ≤ m2 - 1

k(2n) = 3×2(n-1)

k(5n) = 4×5n

k(2×5n) = 6n

n > 2라면, k(10n) = 15×10(n-1)

이 문제에 적용하면, 나머지가 10^6이기에 15*10^5가 이 문제의 주기가 된다.

따라서 주기를 이용하여 문제를 해결하면 아래 결과와 같다.

(for문에서 주기만큼만 구해서 답을 구하면 된다.)

소스 코드 : 

import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
         
    public static void main(String[] args)
    {
        
                BigInteger a = new BigInteger("1");
                BigInteger b = new BigInteger("1");
                BigInteger c = new BigInteger("2");
         
                Scanner sc = new Scanner(System.in);
                
                long n;
                n = sc.nextLong();
                
                if(n == 0)
                    System.out.println(0);
                else if(n == 1)
                    System.out.println(1);
                else if(n == 2)
                    System.out.println(1);
                
                else
                {
                    for(long i = 3; i <= n % 1500000; i ++)
                    {
                        c = (b.add(a)).mod(BigInteger.valueOf(1000000));
                        c = c.mod(BigInteger.valueOf(1000000));
                        a = b.mod(BigInteger.valueOf(1000000));   
                        b = c.mod(BigInteger.valueOf(1000000));
                    }
                    System.out.println(c.mod(BigInteger.valueOf(1000000)));
                }
          
    }
    
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>