Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
SPFIBO - Fibonacci Sequence |
Fibonacci sequence is defined as follow: F1 = 1, F2 = 2, Fi = Fi-1 + Fi-2 (i > 2).
Each natural number X can be expressed by the maximum numbers that are less than or equal to X in Fibonacci sequence: X = a1xF1 + a2xF2 + … Therefore, in Fibonacci system, X is known as: anan-1…a1. For example, 1 = 1F, 2 = 10F, etc. If we write all natural numbers successively in Fibonacci system, we will obtain a sequence like this: 1_1_0… This is called “Fibonacci bit sequence of natural numbers”.
Your task is counting the numbers of times that bit 1 appears in the first N bits of this sequence.
Input
Line 1: An integer N (1 <= N <= 1015)
Output
Line 1: An integer K is the result
Example
Input:
2
Output:
2
Được gửi lên bởi: | HNUE |
Ngày: | 2010-11-16 |
Thời gian chạy: | 0.102s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED |
Nguồn bài: | Anh Hiếu |
hide comments
2019-09-02 05:58:43
Last edit: 2019-09-02 05:58:59 |
|
2015-06-18 01:28:25 Stupid Dog
I like Vietnamese |