문제링크: 백준 9471 피사노 주기
“ 피보나치 수열을 m으로 나눈 나머지가 P길이의 주기를 가진다. “
피보나치 수열을 3으로 나누었을 때, 길이 8의 주기를 나타낸다.
k(m)을 반복하는 부분수열의 길이라고 했을 때, k(3) == 8 이다.
주기의 길이가 p이면, n번째 피보나치 수를 mod으로 나눈 나머지는 n%p 번째 피보나치수를 mod로 나눈 나머지와 같다.
주기를 이루는 숫자를 저장하는 벡터 v를 둔다고 생각해보자 (mod으로 나눈 나머지를 저장한다)
나누는 숫자 mod은 2 이상의 숫자가 주어진다
mod가 2일 때, 피보나치 수1을 2로 나누면 나머지가 1이다. v[0] = 0, v[1] = 1, v[2] = 1 가 된다.
주기의 앞 부분은 확실히 0, 1 순으로 시작하니까. 0, 1 이 연속으로 나오면 주기가 반복되는 지점임을 알 수 있다.
그래서 벡터 v는 필요 없고 숫자 m1, m2만 필요하다.
#include <bits/stdc++.h>
#define endp '\n';
using namespace std;
int p, n, m;
int pisano(int mod){
int cnt = 0; // cnt 번째 피보나치 수
int m1 = 0, m2 = 1; // 0과 1이 순서대로 나오면, 주기 발견.
int tempsum = 0;
while(1){
tempsum = m1 + m2;
m1 = m2;
m2 = tempsum % mod;
cnt++;
if(m1 == 0 && m2 == 1) break;
}
return cnt;
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> p;
for(int i = 1; i <= p; i++){
cin >> n >> m;
cout << n << ' ' << pisano(m) << endp;
}
return 0;
}
참고
백준 포스팅 피보나치 수를 구하는 여러가지 방법
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 피보나치 수 백준 2747번 c++ (0) | 2022.02.08 |
|---|---|
| 피보나치 수 3 백준 2749번 c++ (0) | 2022.02.08 |
| 1로 만들기2 백준 12852 c++ (0) | 2022.02.04 |
| 피보나치 수2 백준 2748 c++ (0) | 2022.02.04 |
| 카드 백준 11652 c++ (0) | 2022.02.04 |