### otajonov_sherzod's blog

By otajonov_sherzod, history, 3 months ago,

Hey nerds,

so i have been encountering quite a lot of comments(like memes or just regular comments) that are not in english/russian. This usually annoys me to be honest. I believe we should respect codeforces enough to use the recommended languages(russian or english). Some people even say "use some translation tool/extension" when you ask them not to use non-english/non-russian language. Well, to those who think that way, maybe problem setters should make contests in their native language and ask participants to "use some translation tool/extension" to understand the statement, Dont you think? and everyone should comment/write blogs in their own language right?

So what I wanted to say is that lets use English or Russian and not complain about getting downvotes for "just a meme"(which only certain people understand)

cheers.

• +25

By otajonov_sherzod, history, 5 months ago,

Hey guys,

So there is this problem on acmp.ru 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 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)


#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();
}



I didnt include some stuff like bigint struct, because code would be like 400/500 lines long with it.

### Attempt 2(AC)


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);



### Attempt 3( WA on test 3)


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);



So, I'm wondering how we could get AC with c++ for this problem, and if its possible to fix the precision error of this second approach.