FIBPOL - Fibonacci Polynomial
Let F(n) be the nth member of the Fibonacci sequence:
F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2) (n > 1)
Consider the following Fibonacci polynomial:
A(x) = x F(1) + x2 F(2) + x3 F(3) + ... + xn F(n) + ... = sigma(n = 0 to infinity) xn F(n)
Amazingly,
A(1/2) = 1/2 + 1/22 + 2/23 + 3/24 + .... + F(n)/2n + ... = 2
In this problem, we only considering the non-negative-integer 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 yields a rational x, 0 otherwise
Example
Input: 5 0 1 2 3 4 Output: 1 0 1 0 0
hide comments
|
akhand_mishra:
2019-12-05 10:14:38
credits to project Euler |
|
hacking_bot:
2018-03-20 14:10:19
For Those in doubt refer Project Euler problem 137
|
|
anirudnits:
2017-10-31 09:36:16
is Ax always an integer? |
|
bolderic:
2017-08-23 03:34:28
Have to say I got a feeling back to my senior high school doing some hard sequence problem |
|
holmesherlock:
2017-04-01 21:45:31
excellent prob,,figured out the solution very early but getting it accepted costed me more than 20 WA.. |
|
Aditya Paliwal:
2017-02-01 16:25:30
Last edit: 2017-02-01 17:26:01 |
|
spartax:
2016-12-01 17:35:01
for c/cpp users, use long double |
|
rahulpadhy:
2016-08-17 08:02:48
Hey Piyush.. This is my submission id : http://www.spoj.com/submit/FIBPOL/id=17521569
|
|
Min_25:
2016-06-10 16:13:46
Almost the same as Project Euler 137.
|
|
Piyush Kumar:
2016-06-10 15:18:09
Test cases have been updated. Sorry for the inconvenience! |
Added by: | Piyush Kumar |
Date: | 2015-09-04 |
Time limit: | 1s-3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY SCM qobi |
Resource: | Project Euler |