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.
In the third solution, checking around 2 neighbouring numbers of the root would do.
Standard sqrt might produce incorrect values, so you can use additional binary searches instead.
There is one pretty easy and beautiful way to solve this problem (check whether number $$$N$$$ is perfect square) without using sqrt functions (which are not precise). Pick some random number $$$M$$$ and check whether $$$N$$$ gives correct quadratic residue modulo $$$M$$$. If no, $$$N$$$ can't be perfect square. Repeat that many times. If no contradiction was found, $$$N$$$ will be (with very high probability) perfect square.
In that very problem, checking all $$$M$$$ in range $$$[3, 20]$$$ is enough to get accepted. code.
Why does attempt 2 give you AC and not TLE?
The time limit is 8 seconds which is very large so maybe thats why.
Hello hashing?
There is an easier way to solve similar problems. Calculate all the fibonacci numbers from 0 to 106 (less is enough for this problem) and store them modulo M in a map/set. Then for any input number X, just check if X % M is in the map/set. M can be any large prime for the sake of simplicity.
Works for fibonacci, factorial, polynomials and what not.