同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

10070_HowmanyFibs_

2022-5-16 18:16| 发布者: Hocassian| 查看: 79| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504514249599-Problem List-采集的数据-后羿采集器.html

Pro.ID

10070

Title

How many Fibs?

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=10070

AC

Submit

141

Ratio

17.02%

时间&空间限制

Time Limit: 400/200 MS (Java/Others) Memory Limit: 131072/32768 K (Java/Others)

描述

Recall the definition of the Fibonacci numbers:

f ₁ := 1
f ₂ := 2
f _n := f _n-1 + f _n-2 (n ≥ 3)

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b].

输入

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a=b=0. Otherwise, a ≤ b ≤ 10¹⁰⁰. The numbers a and b are given with no superfluous leading zeros.

输出

Description

Recall the definition of the Fibonacci numbers:

f ₁ := 1
f ₂ := 2
f _n := f _n-1 + f _n-2 (n ≥ 3)

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b].

Input

Output

For each test case output on a single line the number of Fibonacci numbers f _i with a ≤ f _i ≤ b.

Sample Input

10 100
1234567890 9876543210
0 0

Sample Output

5
4

Source

Ulm Local 2000

样例输入