otajonov_sherzod's blog

By otajonov_sherzod, history, 5 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +27
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by otajonov_sherzod (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

In the third solution, checking around 2 neighbouring numbers of the root would do.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Standard sqrt might produce incorrect values, so you can use additional binary searches instead.

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Why does attempt 2 give you AC and not TLE?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The time limit is 8 seconds which is very large so maybe thats why.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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.