Cod sursa(job #1938741)
Utilizator | Alex Enache Alex18mai | Data | 25 martie 2017 10:20:43 |
---|---|---|---|
Problema | Al k-lea termen Fibonacci | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.63 kb |
#include <fstream>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
int dp[3000014];
int main()
{
int n;
cin>>n;
dp[1]=1;
dp[2]=1;
if (n<=1000000){
for (int i=3; i<=n; i++){
dp[i]=((dp[i-1]%666013)+(dp[i-2]%666013))%666013;
}
cout<<dp[n];
}
else{
int x;
for (int i=3; i<=4*666013; i++){
dp[i]=((dp[i-1]%666013)+(dp[i-2]%666013))%666013;
if (dp[i-1]==1 && dp[i]==1){
x=i-2;
break;
}
}
cout<<dp[n%x];
}
return 0;
}