[백준] 9471번 피사노 주기

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

9471번: 피사노 주기

 

문제 : 

m 이라는 숫자가 주어졌을 때 

 

피보나치 수열에서 m 으로 나누었을 때의 나머지 값이 수열을 이룬다고 한다. 

이 때 이루는 수열의 크기를 구하는 문제 

 

---

수열 시작이 1, 1, ... 으로 시작하므로 

다음 나머지 값이 1, 1이 되는 시점을 찾으면 된다. 

 

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringBuilder builder = new StringBuilder();
        
        for(int i = 0; i<n; i++) {
            String[] tmp = reader.readLine().split(" ");
            int m = Integer.parseInt(tmp[1]);
            
            int a = 1;
            int b = 1;
            int count = 0;
            
            while(true) {
                int next = (a + b) % m;
                a = b;
                b = next;
                count ++;
                
                if (a == 1 && b == 1) {
                    break;
                }
            }
            
            builder.append(i + 1).append(" ").append(count).append("\n");
        }
    
        System.out.println(builder);
    }
}