기본 콘텐츠로 건너뛰기

2749 : 피보나치 수3 [C++]

입력이 1,000,000,000,000,000,000으로 말도 안되게 큰 수!

방법을 모르겠어서 도움을 받았다.

피보나치 수를 mod한 수들은 일정한 주기가 있다!


입력에 따라 주기가 다른데 1,000,000,000,000,000,000의 주기를 찾아보면 1,500,000이다.


int fibonacci(long long n)
{
 vector<int> Fib;
 Fib.push_back(0);
 Fib.push_back(1);
    
        if(n >= 1500000)
           n %= 1500000;
       
 for (int i = 2; i <= n; i++)
  Fib.push_back((Fib[i - 2]%1000000 + Fib[i - 1]%1000000)%1000000);
 
 return Fib[n];
}
<소스 코드>

*문제 출처 : BAEKJOON ONLINE JUDGE
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

11478 : 서로 다른 부분 문자열의 개수 (미제) [C++]

# include < iostream > # include < vector > # include < string > using namespace std ; int main ( ) { string sInput ; getline ( cin , sInput , '\n' ) ; int Time = 1 ; int Count = 0 ; vector < string > Storage ; for ( int i = 0 ; i < sInput . size ( ) ; i + + ) { for ( int j = 0 ; ( j + Time - 1 ) < sInput . size ( ) ; j + + ) Storage . push_back ( sInput . substr ( j , Time ) ) ; Time + + ; } bool * Visited = new bool [ Storage . size ( ) * sizeof ( bool ) ] ; for ( int i = 0 ; i < Storage . size ( ) ; i + + ) { Visited [ i ] = true ; for ( int j = 0 ; j < Storage . size ( ) ; j + + ) { if ( i ! = j & & Storage [ i ] = = Storage [ j ] ) { Visited [ i ] = false ; Visited [ j ] = true ; break ; } } } for ( int i = 0 ; i < Storage . size ( ) ; i + + ) if ( Visited [ i ] ) Count ...
댓글 쓰기
자세한 내용 보기

6359 : 만취한 상범 (Dynamic Programming) [C++]

# include < iostream > # include < vector > using namespace std ; int Num_of_Divisor ( int n ) { int Count = 0 ; for ( int i = 1 ; i < = n ; i + + ) if ( n % i = = 0 ) Count + + ; return Count ; } int main ( ) { int Testcase ; cin > > Testcase ; while ( Testcase - - ) { int Rooms ; cin > > Rooms ; vector < int > Prisons ; for ( int i = 0 ; i < Rooms ; i + + ) Prisons . push_back ( 0 ) ; for ( int i = 1 ; i < Prisons . size ( ) + 1 ; i + + ) { if ( ( Num_of_Divisor ( i ) % 2 ) = = 0 ) Prisons [ i - 1 ] = 0 ; else Prisons [ i - 1 ] = 1 ; } int Fleer = 0 ; for ( int i = 0 ; i < Prisons . size ( ) ; i + + ) if ( Prisons ...
댓글 쓰기
자세한 내용 보기

1520 : 내리막길(미제) (Dynamic Programming) [C,C++]

답은 알맞게 나오는 데 시간이 자꾸 초과된다. 3시간 째 붙잡고 있지만 플러드 필 문제로 밖에 생각이 안되는 데 플러드 필을 사용하면 시간이 오바가 나고.. 경로의 수를 각 배열 인덱스에 저장하면서 나아가는 것 같기도 한데, 사실 상 이것도 플러드 필과 다를 바 없어서 내일 시험 끝나고 다른 방법을 고안해봐야할 것 같다.
댓글 쓰기
자세한 내용 보기