fork download
copy 
  1. /*Dãy số Fibonacci được định nghĩa Fn = Fn-1 + Fn-2, n>1 và F0 = 0, F1 = 1. Dưới đây là một số số Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21…
  2.  
  3. Nhiệm vụ của bạn là tìm số Fibonacci thứ n.
  4.  
  5. Input:
  6.  
  7. Dòng đầu tiên đưa vào số lượng bộ test T.
  8. Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một số nguyên dương n.
  9. T, n thỏa mãn ràng buộc :1 ≤ T ≤ 100; 1≤n≤1000.
  10. Output:
  11.  
  12. Đưa ra kết quả mỗi test theo modulo 109 + 7 theo từng dòng.*/
  13.  
  14.  
  15. #include <bits/stdc++.h>
  16. using namespace std;
  17.  
  18. #define ll long long
  19.  
  20. int mod = 1e9 + 7;
  21.  
  22. struct matran{
  23. 	ll a[2][2];
  24. 	friend matran operator * (matran x, matran y){
  25. 		matran res;
  26. 		for(int i = 0; i < 2; i++){
  27. 			for(int j = 0; j < 2; j++){
  28. 				res.a[i][j] = 0;
  29. 				for(int k = 0; k < 2; k++){
  30. 					res.a[i][j] += x.a[i][k] * y.a[k][j];
  31. 					res.a[i][j] %= mod;
  32. 				}
  33. 			}
  34. 		}
  35. 		return res;
  36. 	}
  37. };
  38.  
  39. matran binpow(matran a, ll k){
  40. 	if(k == 1) return a;
  41. 	matran X = binpow(a, k / 2);
  42. 	if(k % 2 == 0){
  43. 		return X * X;
  44. 	}
  45. 	else return X * X * a;
  46. }
  47.  
  48. int main(){
  49. 	ios::sync_with_stdio(false);
  50. 	cin.tie(nullptr);
  51. 	int t; cin >> t;
  52. 	while(t--){
  53. 		int n; cin >> n;
  54. 		matran x;
  55. 		x.a[0][0] = 1;
  56. 		x.a[0][1] = 1;
  57. 		x.a[1][0] = 1;
  58. 		x.a[1][1] = 0;
  59. 		matran res = binpow(x, n);
  60. 		cout << res.a[0][1] << endl;
  61. 	}
  62. 	return 0;
  63. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
2
2
5
stdout
copy 
1
5
https://ideone.com/Jqc6Kz
Tính số Fibonacci lớn
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!