# DCP-303: Fibonacci Divisor Back to All Problems

Medium Math > Number Theory

Can you find the **nth Fibonacci number**? So easy ! Isn't it ? But can you find the number of Fibonacci numbers which is divisible by **nth** Fibonacci number ?<br> Some Fibonacci numbers from beginning are : 1,1,2,3,5,8,13.... Input: ------ Input starts with an integer T (**1<=T<=200000**), denoting the number of test cases. Each case contains two integers **n** and **k** (**3 <= n <=200000 and 3<=k<=200000**) . You have to find how many Fibonacci numbers (less than or equal to **kth** Fibonacci numbers) are divisible by nth fibonacci numbers. If n=4 and k=7 then the 4th fibonacci number is 3 and there is only 1 fibonacci number less than or equal to 7th fibonacci numbers which are divided by 3 and that is 3. So the output should be 1. Output: ------- For every test case print how many fibonacci numbers are there ( less than or equal to kth fibonacci numbers ) which are divisible by nth fibonacci number. Sample Input ------------ 1 4 7 Sample Output ------------- 1

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 1.00 Go 1.00 Java 1.00 JavaScript 1.00 Objective-C 1.00 Perl 1.00 PHP 1.00 Python 1.00 Python3 1.00 Ruby 1.00 VB.Net 1.00

# 53/111

Solve/Submission

### Ranking

# User Language Timing
01 Morass Cpp14 0.02s
02 Robbinb1993 Cpp14 0.02s
03 FahimSifnatul Cpp 0.05s
04 feodorv C 0.05s
05 mhiceiuk Cpp 0.05s
06 Saimum_140128 Cpp 0.05s
07 rayhan50001 C 0.05s
08 rummanrakib11 Cpp14 0.06s
09 sazal_dev Cpp 0.06s
10 monir769 Cpp 0.06s
11 mahbub07 Cpp 0.06s
12 xb_saykat Cpp 0.06s
13 pulak_ict_mbstu Cpp 0.06s
14 codebreaker007 Cpp 0.06s
15 kissu_pari_na Cpp 0.06s
16 nasib_mbstu Cpp14 0.06s
17 ssavi Cpp 0.06s
18 subhashis_cse Cpp 0.06s
19 Bruteforcekid Cpp 0.06s
20 fayedanik Cpp 0.06s
21 anik_JU Cpp 0.06s
22 dot_0 Cpp 0.06s
23 tlcakash Cpp 0.06s
24 atqrhmn Cpp 0.07s
25 haasib Cpp 0.25s
26 clkjwdhc Cpp 0.27s
27 wajiul Cpp 0.33s
28 tariqiitju Cpp 0.33s
29 Silent_Warrior Cpp 0.35s
30 Shamim_A Cpp 0.35s
31 nurshuvo51 Cpp 0.35s
32 onucsecu Cpp 0.36s
33 kzvd4729 Cpp 0.37s
34 Ansarul_14 Cpp 0.38s
Feedback