This solution >>> https://www.codechef.com/viewsolution/4569721

As the number in the input is of 1000 digits how this solution got AC ?

Even long long won’t be able to hold such a large value so how this solution got accepted ??

lol,seems like test cases are pretty weak.

That’s what I’m wondering. How can a number of 1000 digits fit in long long.

Its mentioned by the problem setter @vineetpaliwal in the comments of the editorial that such solutions (including the Tester’s solution) are storing the fibonacci number in the **64-bit** int data type and letting the overflow occur. After overflow what remains is the value of that number mod **2^64**. It then check if any fibonacci number gives the same value mod **2^64** or not. This is similar to **hashing** technique.

This method assumes that no **2** fibonacci numbers within the given range give the same value mod **2^64** i.e. no collisions.

This method is not correct but passes because the test cases might be weak.

Read the interesting “comments” int the editorial page. Wondering how the solvers got away with it.

Oh, Now I got it thanks a lot but isn’t it wrong to let such an incorrect solution to get AC. And I was reading the editorial too and there are many cases at which this solution gives wrong answer.

lol,I found the editorial too. The comments are really interesting.

@c_utkarsh I think you mean to say that the method assumes no hash collision occurs between a Fibonacci and a non-Fibonacci number, rather than 2 Fibonacci numbers.

Also the numbers are being stored modulo 2^{64}, and not 2^{64}-1.

Exactly. And about the mod, the tester’s solution uses `unsigned long long`

whose limit is 2^64 - 1 and thus the numbers are being stored mod 2^64. Thanks for correcting. Updated now.