Story
Given a number K, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them.
Output two separate numbers, F and D, where F is the smallest fibonacci number and D is the smallest number other than 1 which divides K and F.
Input Format
First line of the input contains an integer T, the number of testcases.
Then follows T lines, each containing an integer K.
Output Format
Output T lines, each containing the required answer for each corresponding testcase.
Sample Input
3
3
5
161
Sample Output
3 3
5 5
21 7
Explanation
There are three testcases. The first test case is 3, the smallest required fibonacci number 3. The second testcase is 5 and the third is 161. For 161 the smallest fibonacci numer sharing a common divisor with it is 21 and the smallest number other than 1 dividing 161 and 7 is 7.
Constraints :
1 <= T <= 5
2 <= K <= 1000,000
The required fibonacci number is guranteed to be less than 10^18.
My Answer: (I am no sure if it is correct.)
#include "stdafx.h"
#include <iostream>
using namespace std;
int fb(int i);
int _tmain(int argc, _TCHAR* argv[])
{
int count = 0;
cin >> count;
int *input = new int[count];
for (int i = 0; i<count; i++)
{
cin >> input[i];
}
for (int i = 0; i<count; i++)
{
int k = 1;
int fbNumber = 1;
while (fbNumber <= input[i])
{
for (int x=2; x<=fbNumber; x++)
{
if (fbNumber % x == 0 && input[i] % x == 0 )
{
cout << input[i] << " " << fbNumber << endl;
}
}
k++;
fbNumber = fb(k);
};
}
return 0;
}
int fb(int i)
{
if (i<=1)
return 1;
if (i==2)
return fb(1);
return fb(i-1) + fb(i-2);
}
Reference:
https://amazon.interviewstreet.com/challenges/dashboard/#problem/4fd653336df28
