문제

아이디어

피보나치 수열을 이용한 흔한 문제처럼 보이지만, n의 범위가 이상하다.
1,000,000,000,000,000,000, 즉 100경짜리 변수다. 이 범위를 완전탐색할 수는 없는 노릇.

여기서 잠깐, 태그에 있는 피사노 주기는 무엇일까?

피사노 주기

피보나치 수열에서 임의의 정수m으로 나눈 나머지가 반복되는 주기를 말한다.
π(m) = F(n) mod m 이라고 할 때, 피사노 주기는 모든 자연수 m에 대해서 항상 존재하며, 유한하다.
π(0) = 0, π(1) = 1 이므로, F(p) mod m = 0, F(p+1) mod m = 1일 때 피사노 주기는 p이다.

그렇다면 이 피사노 주기를 구한다면 쉽게 문제를 풀 수 있다.

N의 범위를 고려했을 때, BigInteger에 저장해야 함에 유의하자.

소스코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static BigInteger N;
    static List<Integer> fibo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = new BigInteger(br.readLine());
        fibo = new ArrayList<>();

        fibo.add(0);
        fibo.add(1);

        int cur, prev, pisano;
        prev = 1;
        while (true) {
            cur = (fibo.get(fibo.size() - 1) + fibo.get(fibo.size() - 2)) % 1000000;
            if (prev == 0 && cur == 1) {
                pisano = fibo.size() - 1;
                break;
            }
            fibo.add(cur);
            prev = cur;
        }
        N = N.mod(BigInteger.valueOf(pisano));
        System.out.println(fibo.get(N.intValue()));
    }
}

채점결과

추가하자면 M=1,000,000 일때의 피사노 주기는 1,500,000이다.