기본 콘텐츠로 건너뛰기

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
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

1149 : RGB Street Coloring (Dynamic Programming) [C,C++]

The key to this problem lies in understanding the principles. Let me explain the algorithm to solve the problem by using DP. First, you need the same storage space like input data's size. When you draw any color of the nth house, the space will contain the minimum value. If you paint the red in the second house, this value is sum of blue or green of the first house.  You must use DP because you must use the previous value.  Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.  If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.  Therefore, the minimum value can be found in the value of the storage space (n-1) index. <pesudo code> *Source of the problem =  https://www.acmicpc.net/problem/1149 *문제 출처 : BAEKJOON ONLINE JUDGE
댓글 쓰기
자세한 내용 보기

11004 : K번째 수 [C++]

# include < iostream > # include < cstdio > # include < algorithm > int main ( ) { int * Number = new int [ 5000000 ] ; int N , K ; scanf ( " %d %d " , & N , & K ) ; for ( int i = 0 ; i < N ; i + + ) scanf ( " %d " , Number [ i ] ) ; std :: sort ( Number , Number + N ) ; printf ( " %d " , Number [ K - 1 ] ) ; return 0 ; }
댓글 쓰기
자세한 내용 보기

10250 : ACM 호텔 [C++]

# include < iostream > # include < vector > using namespace std ; int main ( ) { int testcase ; cin > > testcase ; while ( testcase - - ) { int W , H ; cin > > H > > W ; int N ; cin > > N ; int cnt = 0 ; int i , j ; bool BreakPoint = false ; for ( i = 1 ; i < = W ; i + + ) { for ( j = 1 ; j < = H ; j + + ) { if ( + + cnt = = N ) BreakPoint = true ; if ( BreakPoint ) break ; } if ( BreakPoint ) break ; } if ( i < 10 ) cout < < j < < " 0 " < < i < < endl ; else cout < < j < < i < < endl ; } }
댓글 쓰기
자세한 내용 보기