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 Setter:

Kazi Sohan

Please login to submit solution to this problem.

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

Problem Stats




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

Your feedback is our precious!

Or call +88 02 9853138 for support