[HSG-QH_TXCL_NA_24] Dãy số FIBO
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python
Dây Fibonaci là một dãy số nổi tiếng, với nhiều hình ảnh và ứng dụng đẹp đẽ xuất hiện rất nhiều trong cuộc sống quanh ta. Xuất phát từ ~2~ số ~0~ và ~1~, các số tiếp theo được xác định bằng cách tính tổng ~2~ số lớn nhất đã xuất hiện trong dãy. Một số giá trị đầu tiên trong dãy Fibonaci là ~0, 1, 1, 2, 3, 5, 8, 13, ...~.
Yêu cầu
Với số nguyên dương ~n~ cho trước, hãy viết chương trình xác định giá trị số Fibonaci thứ ~n~ (xem ~0~ là số thứ nhất của dãy).
Dữ liệu đầu vào
Gồm một dòng duy nhất chứa sẽ nguyên dương ~n~ ~(0 < n \le 10^6)~.
Dữ liệu đầu ra
Gồm một số nguyên duy nhất là giá trị vừa tìm được. Số Fibonaci thứ ~n~ có thể có giá trị rất lớn, bạn chỉ cần in ra số dư của nó trong phép chia cho ~10^9 + 1~.
Ràng buộc dữ liệu
- Có 50% số điểm với ~1 \le n \le 10^4~;
- Có 50% số điểm với ~1 \le n \le 10^6~.
Ví dụ
Ví dụ 1
INPUT
9
OUTPUT
21
Bình luận
hi ae