Hey guys,↵
↵
So there is [this problem on acmp.ru](https://acmp.ru/asp/do/index.asp?main=task&id_course=4&id_section=27&id_topic=285&id_problem=1863) that asks you to determine if a given number `N` is a fibonacci number where $ 1<= N <= 10^{100000}$. ↵
↵
Time: 8 sec. ↵
Memory: 16 MB↵
↵
I tried to solve this with [this bigint](https://gist.github.com/ar-pa/957297fb3f88996ead11) in c++ using brute force approach. But it gave TLE on test 14.↵
Then I switched to python, did the same thing, and got AC. After some googling, I also found that a number `N` is a fibonacci number if $ 5*N^2+4 $ or $ 5*N^2-4 $ is a perfect square. So i tried it with python but it got WA on test 3, probably because of some precision errors.↵
↵
Here are my attempts:↵
↵
### Attempt 1 (TLE on test 14)↵
↵
<pre class="prettyprint">↵
↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
int main(){↵
string r = "", line;↵
ifstream inp;↵
ofstream outp;↵
inp.open ("INPUT.txt");↵
outp.open ("OUTPUT.txt");↵
getline (inp, line);↵
bigint x = line, a = 0, b = 1, tmp;↵
while(a < x){↵
tmp = b; b = a+b; a = tmp;↵
}↵
if(a == x) r = "YES\n";↵
else r = "NO\n";↵
↵
outp << r;↵
inp.close(); outp.close();↵
}↵
↵
</pre>↵
↵
I didnt include some stuff like bigint struct, because code would be like 400/500 lines long with it.↵
↵
### Attempt 2(AC)↵
<pre class="prettyprint">↵
↵
↵
from math import sqrt↵
with open("INPUT.TXT") as inp:↵
r='';↵
x=int(next(inp));↵
a, b = 0, 1;↵
while(a < x):↵
a, b = b, a + b;↵
if(a == x): r = 'YES';↵
else: r = 'NO';↵
with open("OUTPUT.TXT", 'w') as out:↵
out.write(r);↵
↵
</pre>↵
↵
↵
### Attempt 3( WA on test 3)↵
↵
<pre class="prettyprint">↵
↵
from math import sqrt↵
↵
with open("INPUT.TXT") as inp:↵
r = '';↵
x = int(next(inp));↵
n = 5*x**2; sq1 = int(sqrt(n+4)); sq2 = int(sqrt(n-4));↵
if(sq1*sq1 == n+4 or sq2*sq2 == n-4): r = "YES";↵
else: r = "NO";↵
with open("OUTPUT.TXT", 'w') as out:↵
out.write(r);↵
↵
</pre>↵
↵
So, I'm wondering how we could get AC with python for this problem, and if its possible to fix the precision error of this second approach.
↵
So there is [this problem on acmp.ru](https://acmp.ru/asp/do/index.asp?main=task&id_course=4&id_section=27&id_topic=285&id_problem=1863) that asks you to determine if a given number `N` is a fibonacci number where $ 1<= N <= 10^{100000}$. ↵
↵
Time: 8 sec. ↵
Memory: 16 MB↵
↵
I tried to solve this with [this bigint](https://gist.github.com/ar-pa/957297fb3f88996ead11) in c++ using brute force approach. But it gave TLE on test 14.↵
Then I switched to python, did the same thing, and got AC. After some googling, I also found that a number `N` is a fibonacci number if $ 5*N^2+4 $ or $ 5*N^2-4 $ is a perfect square. So i tried it with python but it got WA on test 3, probably because of some precision errors.↵
↵
Here are my attempts:↵
↵
### Attempt 1 (TLE on test 14)↵
↵
<pre class="prettyprint">↵
↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
int main(){↵
string r = "", line;↵
ifstream inp;↵
ofstream outp;↵
inp.open ("INPUT.txt");↵
outp.open ("OUTPUT.txt");↵
getline (inp, line);↵
bigint x = line, a = 0, b = 1, tmp;↵
while(a < x){↵
tmp = b; b = a+b; a = tmp;↵
}↵
if(a == x) r = "YES\n";↵
else r = "NO\n";↵
↵
outp << r;↵
inp.close(); outp.close();↵
}↵
↵
</pre>↵
↵
I didnt include some stuff like bigint struct, because code would be like 400/500 lines long with it.↵
↵
### Attempt 2(AC)↵
<pre class="prettyprint">↵
↵
↵
from math import sqrt↵
with open("INPUT.TXT") as inp:↵
r='';↵
x=int(next(inp));↵
a, b = 0, 1;↵
while(a < x):↵
a, b = b, a + b;↵
if(a == x): r = 'YES';↵
else: r = 'NO';↵
with open("OUTPUT.TXT", 'w') as out:↵
out.write(r);↵
↵
</pre>↵
↵
↵
### Attempt 3( WA on test 3)↵
↵
<pre class="prettyprint">↵
↵
from math import sqrt↵
↵
with open("INPUT.TXT") as inp:↵
r = '';↵
x = int(next(inp));↵
n = 5*x**2; sq1 = int(sqrt(n+4)); sq2 = int(sqrt(n-4));↵
if(sq1*sq1 == n+4 or sq2*sq2 == n-4): r = "YES";↵
else: r = "NO";↵
with open("OUTPUT.TXT", 'w') as out:↵
out.write(r);↵
↵
</pre>↵
↵
So, I'm wondering how we could get AC with python for this problem, and if its possible to fix the precision error of this second approach.
