Nội dung Bài tập
- Mã:
-
Div2.MINIGAME31.3:
SUMFIBO
- Tên:
- Tính Tổng Fibonacci
- Dạng thi:
- oi
- Thang điểm:
- 30 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- HUSCNMT
Chắc tất cả chúng ta ai ai cũng biết dãy số Fibonacci.
Quảng cáo
Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó.
Công thức truy hồi của dãy Fibonacci là:
Rentt hôm nay cũng được học về dãy số Fibonacci này ở trường nhưng, nhưng vì là học sinh chuyên Tin, nên thầy giáo muốn thử thách các học trò của mình trong đó có Rentt bằng cách đưa ra bài toán đơn giản như sau:
Nhập vào 1 số N, thầy muốn các học trò của mình tính tổng N các số Fibonacci này.
Rentt rất giỏi tính toán nhưng vì số quá lớn nên Rentt đành bó tay.. Vì thế Rentt nhờ các bạn Upcoder giúp cậu ấy để giải quyết giúp bài này.
Là một Competitive Programming, các bạn có thể giúp Rentt được không?
- Input
Dòng đầu tiên chứa 1 số N ( 1 <= N <= 1015 ).
- Output
Kết quả của tổng đó. Vì tổng có thể rất lớn nên chỉ lấy phần dư cho 109 + 7.
| Input | Output |
|---|---|
5 | 12 |
Giải thích: 5 số Fibonacci đầu tiên là: 1 1 2 3 5 => tổng là 12
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <bits/stdc++.h>using namespace std;//Tự cho là gồm 4 chữ số , vì đề bài k n...