C++에서 N번째 피보나치 수의 마지막 두 자리를 찾는 프로그램

이 문제에서 우리는 숫자 N을 받습니다. 우리의 임무는 C++에서 N번째 피보나치 수의 마지막 두 자리를 찾는 프로그램을 만드는 것입니다.

문제 설명

N번째 피보나치 수의 마지막 두 자리(즉, 두 개의 LSB)를 찾아야 합니다. 문제를 이해하기 위해 예를 들어 보겠습니다.

입력 :N =120

출력 :81

솔루션 접근 방식

간단한 솔루션은 직접 피보나치 공식을 사용하여 N번째 항을 찾는 것입니다. 그러나 이 방법은 N이 큰 수일 때 실현 가능하지 않습니다. 따라서 이를 극복하기 위해 마지막 두 자리 숫자가 300항 후에 반복되는 피보나치 수열의 속성을 사용할 것입니다. 즉. 75번째 단어의 마지막 두 자리는 975번째 단어의 숫자와 같습니다.

즉, 300까지 작업하면 가능한 모든 조합이 제공되고 사용할 용어를 찾기 위해 300으로 숫자의 모드를 찾을 수 있습니다.

예시

#include <iostream>
using namespace std;
long int fibo(int N){
   long int a=0,b=1,c;
   for(int i=2; i<= N;i++) {
      c=a+b; a=b; b=c;
   }
   return c;
}
int findLastTwoDigitNterm(int N) {
   N = N % 300;
   return ( fibo(N)%100);
}
int main() {
   int N = 683;
   cout<<"The last two digits of "<<N<<"th Fibonacci term are "<<findLastTwoDigitNterm(N);
   return 0;
}

출력

The last two digits of 683th Fibonacci term are 97