Special Fibonacci Problem Code: FIBXOR01
Sankalp recently learned Fibonacci numbers and now he is studying different algorithms to find them. After getting bored of reading them, he came with his own new type of numbers. He defined them as follows:
- f(0) = a;
- f(1) = b;
- f(n) = f(n-1) ^ f(n-2); when n>1, where ^ denotes the bitwise xor operation.
You are given three integers a,b and n , calculate f(n).
Input
The input contains one or more independent test cases.
The first line of input contains a single integer T (1≤T≤103), the number of test cases.
Each of the T following lines contains three space-separated integers a, b, and n (0≤a,b,n≤109) respectively.
Output
For each test case, output f(n).
Constraints
Sample Input
4
86 77 15
93 35 86
92 49 21
62 27 90
Sample output
86
126
92
62
SOlution :
This question looks like of recursion but if we think of it and solve the equation further
we will f(n) = f(n%3),that's why i first found n = n%3 , then make three values of n because now , n can only be 0 ,1 , 2.
how to solve the equation the equation
f(n) = f(n-1)^f(n-2); .............eqn1
repacing n by n+1 ,
we get ,
f(n+1) = f(n)^f(n-1) ..................eqn2
adding eqn1 and eqn 2
we get ,
f(n)^f(n+1) = f(n-1)^f(n-2)^f(n)^f(n-1)
which is equal to
f(n) ^ f(n+1) = f(n) ^ f(n-2)
=> f(n+1) = f(n-2)
now replacing n+1 by n ,
f(n) = f(n-3); ................a
also , f(n-3) = f(n-6) right? .................b
f(n-6) = f(n-9) ................c
and so on ,
then on adding a+b+c+........
f(n) = f(n-3*x) where x is a random number such that 0< n - 3*x < 3 , that is it can simply the remainder after dividing it with 3.
f(n) = f(n%3);
#include <iostream>
using namespace std;
long long int f(int);
int main()
{
int t ;
cin >> t;
while(t--)
{
long int a , b , n ;
cin >> a >> b >> n;
long int d = a^b;
n = n %3 ;
if(n== 0)
cout << a << "\n";
if( n==1 )
cout << b << "\n";
if(n == 2)
cout << d << "\n";
}
return 0;
}
Comments
Post a Comment