There is a task, I solved it and while the program works with small numbers the answers are displayed correctly. But when we take larger numbers the answers stop counting.

I used variables of type unsigned __int64 . Still, large sequences are wrong. What could be the problem?

Task: A sequence of numbers, defined by the formula:

 F (0) = a F (1) = b F (N) = F (N-1) + F (N-2)

In each row, we are given a , b , N and M

It is necessary to derive the remainder of the N -th term of the sequence divided by 10 M.

Examples of I / O:

enter image description here

code:

 #include <iostream> #include <stdio.h> using namespace std; int main() { unsigned __int64 a,b,n,m,sum,po; cin>>a>>b>>n>>m; sum=a+b; po=pow(10,m); if(n==0){cout<<a<<endl;} else if(n==1){cout<<b%po<<endl;} else if(n==2){cout<<sum%po<<endl;} else if(n>=3){ for(unsigned __int64 i=2;i<n;i++) { sum+=b; b=sum-b; } cout<<sum%po<<endl; } return 0; }
  • Would you bring restrictions imposed on the input values ​​... - Harry
  • @Harry let's say I set if (N <1000000001), as in the task. This, after all, should not influence the decision? - rengetsu

1 answer 1

You need to consider not the actual values ​​of the Fibonacci numbers, but their residuals - calculating them immediately along the way. Roughly speaking, the remainder of dividing a certain Fibonacci number is equal to the sum of the residuals of the two previous numbers.

I'm not sure that it will be correct to give a solution to the Olympiad problem, but I think this hint should be enough.

This is a head-on decision; it makes sense to track the periodicity of residuals - and they will definitely be with N greater than 10 2M +1 - this can significantly speed up work for large N. I do not know what time limits - but consider the billion Fibonacci number (in the sense, the remainder) - of maybe not enough. Look here for the leftovers.

  • Thanks a lot, I understood the principle, I will try to solve it. - rengetsu