[Mảng 1 Chiều Cơ Bản]. Bài 57. Cặp số Fibonacci
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho mảng A[] gồm N phần tử bạn hãy đếm xem trong mảng A[] có bao nhiêu cặp số có tổng là 1 số trong dãy số Fibonacci
Lưu ý dãy Fibonacci bắt đầu từ số 0
Đầu vào
Dòng 1 là N : số phần tử trong mảng
Dòng 2 là N số viết cách nhau 1 dấu cách
Giới hạn
1≤N≤10^3
0≤A[i] ≤10^6
Đầu ra
In ra đáp án của bài toán
Ví dụ :
Input 01
5
1 2 3 4 5
Output 01
4
Bình luận
h
Sigma code:
include<bits/stdc++.h>
using namespace std; typedef long long ll; ll a[1003],f[1000006],n; map<ll,bool>found; int main() { ios::syncwithstdio(0); cin.tie(nullptr); cin>>n; for(ll i=1;i<=n;i++) cin>>a[i]; f[0]=0; f[1]=1; found[0]=true; found[1]=true; for(ll i=2;i<=52;i++) { f[i]=f[i-1]+f[i-2]; found[f[i]]=true; } ll cnt=0; for(ll i=1;i<n;i++) for(ll j=i+1;j<=n;j++) { ll sum=a[i]+a[j]; if(found[sum])cnt++; } cout<<cnt<<"\n"; }
DÙNG CÔNG THỨC KIỂM TRA CHO NHANH NHA AE
include <bits/stdc++.h>
using namespace std; using ll = long long; using ull = unsigned long long; bool isPerfectSquare(long long x) { long long s = (long long)floor(sqrt((long double)x)); return s * s == x || (s + 1) * (s + 1) == x; } bool isFibonacci(long long n) { long long a = 5 * n * n + 4; long long b = 5 * n * n - 4; return isPerfectSquare(a) || isPerfectSquare(b); } int main() { ios::syncwithstdio(false); cin.tie(nullptr); int n; cin >> n; int a[n]; for(int &i : a) cin >> i; int dem=0; for(int i = 0; i < n;i++){ for(int j = i+1; j<n; j++){ if(isFibonacci(a[i]+a[j])) dem++; } } cout << dem; return 0; }
ban đầu mình thấy học code thật nhàm chán cho đến khi mình biết được những bài này có cách giải hay ntn ví dụ bày này thay vì chạy fibonacci chay thì mình có thể dùng sàng fibonacci thử nhóe dưới đây là hàm đấy