Consider the fact that for any sequence $G$ with the form of fibonacci, that is: $G_{i+1} = G_i + G_{i-1}$, then $G_i = G_1 \cdot F_i + G_0 \cdot F_{i-1]$. So the problem became to solve two linear equations in integers. Prove it with induction or consider the matrix exponentiation for fibonacci.

You should use Python to avoid overflow (long long isn't sufficient, at least for my implementation). Good Luck!

Consider the case in which n < i, j
That helped me to get AC

-1000 0 0 1 1
My solution do not deal with testcases like this, yet still was accepted. Am I missing something? For those who wonder, my program gives 9079565065540428013 on this testcase lol

If you calculate with formulas, then long long is not enough. You can use __int128. You can't read and write it, but you can cast it to and from other integer types.

intput 4 0 333 0 777
output 0

Use   if(c> 8000000000LL || c< -8000000000LL)  break ; this line in BInary search...


code :
[deleted]

Edited by author 01.06.2018 17:02

Edited by moderator 20.11.2019 22:45

46 1836311903 -46 -1836311903 45

I got wrong ans on test case 2. what is the test case? Please help.

I used the formulas with phi and solved a system of 2 equations to get the coefficients, in python using floats.

Any hint why I get WA8? all tests on the forum work.

for(int m=i+2;m<=j;m++)
    if((m-i)%2==1)
    {
        t2+=t1;
        if(t2<-8000000000LL||(t2>8000000000LL))//Look at this line.
            break;
    }
    else
    {
        t1+=t2;
        if(t1<-8000000000LL||(t1>8000000000LL))//Look at this line.
            break;
    }

----
    Sorry for my bad English

F1 = 1 F4 = 4
what numbers are F2 and F3?

F2 = F1+F0
F3 = 2*F1+F0
F4 = 3*F1+2*F0

F0 == 0.5???

anzhig@inbox.ru

Edited by author 20.07.2012 18:56

The fastest way is to use matrix exponentiation and it is quite simple to understand. The algorithm is O(log n), yes it is that fast!. I got AC with Python 2.7 with 0.046s. Python has an added advantage for this problem since its Integer type can be as big as the RAM of the device being used. With c++ you can still get answers fast, using matrix exponentiation, but the answers are not precise enough, and leads to WA.

Edited by author 29.07.2015 15:42

I killed a lot of time writing the solution in C++, Python, Java. Java gives AC with BigInteger -_-
It is NOT solvable with int64

Got WA2. please respond.

#include <iostream>
#include <conio.h>
using namespace std;

void find(int j, int i, int &k1,int &k2)
{
     if (j==i+1) return;
     else
     {
         int buf = k1;
         k1 = k1 + k2;
         k2 = buf;
         find(j-1,i,k1,k2);
    }
}

int main()
{
     long long Fi, Fj, f1,f2, f3;
     int i,j,n;
     cin>>i>>Fi>>j>>Fj>>n;
    if (j==n)  {cout<<Fj<<endl; return 0;}
    if (i==n)  {cout<<Fi<<endl; return 0;}
     if (i<j)
     {
               int buf = i;
               i = j;
               j = buf;
               buf = Fi;
               Fi = Fj;
               Fj = buf;
    }
     int k1 = 1, k2 = 1;
     f1 = Fj;
     if (i!=j+1)
     {
        find(i-1,j,k1,k2);
        f2 = (Fi - k2*Fj)/k1;
     }
    else
        f2 = Fi;

     int lim;
     if (j<0) lim = n - j -1;
     else
     if (j == 0 ) lim = n;
     else lim = n - j +1;
     for (int count = j +1; count < lim; count++)
    {
         f3 = f1 + f2;
         f1 = f2;
         f2 = f3;
    }
     cout<<f3<<endl;
     return 0;
}

If you use formula in C++, you don't need the long arithmetics. Use long double and you'll get AC.

I tried solve this problem 6 times and 3 of their are WA15,
This WA is expects when uses binsearch, when I replaced type of numbers from long to BigInteger in java, I got AC, in this 15' test intermediate(промежуточные) numbers bigger than 2000000000 or lower than -2000000000, that is why we have wrong answers ))
Good luck!

Edited by author 27.01.2009 21:59

Does anyone what's the test 3?????

I used C++11 with long long type, still cannot pass #15. After changing my code to python 2.7, I got the AC. Since the input range is [-2000000000,2000000000], long long type should not suffer from overflow. Then what's the reason of WA 15?