피사노 주기2 BOJ 2749 피보나치 수 3 www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번엔 피보나치 수 3을 풀어봤다. 입력받는 N이 무려 \(10^{18}\) 이다... 내가 알기에 Long Long int 형이 딱 저 자릿수에 걸치는 걸로 안다. 이 문제는 피사노 주기를 이용해서 풀어야 한다. 피보나치 수열은 어떤 값으로 나눌 경우 특정한 주기를 갖는데 이 문제에서는 나누는 값이 백만으로 매우 작아서 피사노 주기를 이용하여 풀 수 있다. do { int tmp = m1; m1 = m2; m2 = (tmp + m1) % MOD; len++; } while (m1 != 0 .. 2020. 9. 18. 백준 9471 피사노 주기 www.acmicpc.net/problem/9471 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000) www.acmicpc.net 피보나치수열을 m으로 나누면 일정한 주기를 띄게 되는데 그 주기의 길이를 찾는 문제이다. 우선 주기마다 규칙이 있을 거라 판단하고 몇 개의 케이스를 돌려보았다. 이 외에도 몇개를 더 살펴봤지만 1, 0 숫자가 나온 뒤에 다시 주기가 나오는 것을 확인할 수 있다. #include using namespace std; int main() { ios::sync_with_stdio(fals.. 2020. 9. 18. 이전 1 다음
