FIBPOL  Fibonacci Polynomial
Let F(n) be the n^{th} member of the Fibonacci sequence:
F(0) = 0, F(1) = 1,
F(n) = F(n1)+F(n2) (n > 1)
Consider the following Fibonacci polynomial:
A(x) = x F(1) + x^{2} F(2) + x^{3} F(3) + ... + x^{n} F(n) + ....
= sigma(n = 0 to infinity) x^{n} F(n)
Amazingly,
A(1/2) = 1/2 + 1/2^{2} + 2/2^{3} + 3/2^{4} + .... + F(n)/2^{n} + ... = 2
In this problem, we only considering the nonnegativeinteger value of A(x)
. Here are some examples of A(x)
for specific x
.
x  A(x) 

0  0 
sqrt(2)1  1 
1/2  2 
[sqrt(13)2]/3  3 
[sqrt(89)5]/8  4 
Find out if x
is rational with the given value of A(x)
Input
The first line contains T, the number of test cases. The next T lines contains the value of A(x).
0 <= Ax <= 10^17
1 <= T <= 100000
Output
1 if the given Ax yeilds a rational x, 0 otherwise
Example
Input:
5
0
1
2
3
4
Output:
1
0
1
0
0
hide comments
akhand_mishra:
20191205 10:14:38
credits to project Euler 

hacking_bot:
20180320 14:10:19
For Those in doubt refer Project Euler problem 137


anirudnits:
20171031 09:36:16
is Ax always an integer? 

bolderic:
20170823 03:34:28
Have to say I got a feeling back to my senior high school doing some hard sequence problem 

holmesherlock:
20170401 21:45:31
excellent prob,,figured out the solution very early but getting it accepted costed me more than 20 WA.. 

Aditya Paliwal:
20170201 16:25:30
Last edit: 20170201 17:26:01 

spartax:
20161201 17:35:01
for c/cpp users, use long double 

rahulpadhy:
20160817 08:02:48
Hey Piyush.. This is my submission id : http://www.spoj.com/submit/FIBPOL/id=17521569


Min_25:
20160610 16:13:46
Almost the same as Project Euler 137.


Piyush Kumar:
20160610 15:18:09
Test cases have been updated. Sorry for the inconvenience! 
Added by:  Piyush Kumar 
Date:  20150904 
Time limit:  1s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY SCM qobi 
Resource:  Project Euler 