243
Cerința
Șirul lui Fibonacci este definit astfel:
Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2.
Se dă un număr natural n
. Determinați al n
-lea termen al șirului, modulo 666013
.
Date de intrare
Programul citește de la tastatură numărul n
.
Date de ieșire
Programul va afișa pe ecran numărul F
, reprezentând al n
-lea termen al șirului, modulo 666013
.
Restricții și precizări
1 ≤ n ≤ 2.000.000.000
Exemplu
Intrare
6
Ieșire
8
Explicație
Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...
#include <bits/stdc++.h> using namespace std; #define MOD 666013 void produs(long long P[][2] , long long A[][2] , long long B[][2]) { P[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD; P[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD; P[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD; P[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD; } void copiere(long long A[][2] , long long B[][2]) { for(int i = 0 ; i <= 1 ; i++) for(int j = 0 ; j <= 1 ; j++) A[i][j] = B[i][j]; } int fibo(int n) { long long A[2][2] = {{1 , 1} , {1 , 0}} , P[2][2] = {{1 , 0} , {0 , 1}} , B[2][2]; while(n > 0) { if(n % 2 == 1) { produs(B , A , P); copiere(P , B); } produs(B , A , A); copiere(A , B); n /= 2; } return P[0][1]; } int main() { int n; cin >> n; cout << fibo(n); return 0; }
Comentarii