Dãy Fibonacci 6 - Tích Fibo
Đề bài
Dãy Fibonacci được xác định như sau:
- \(F_k=k\) nếu \(0\le k\le 1\)
- \(F_k=F_{k-1}+F_{k-2}\) nếu \(k>1\)
Cho \(t\) số nguyên không âm. Với mỗi số \(n_i\), hãy kiểm tra xem \(n_i\) có thể viết dưới dạng tích của hai số thuộc dãy Fibonacci hay không.
Nói cách khác, cần xác định có tồn tại hai chỉ số không âm \(a\), \(b\) sao cho \(n_i=F_a\times F_b\) hay không.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên \(t\).
\(t\) dòng tiếp theo, dòng thứ \(i\) chứa một số nguyên \(n_i\).
Dữ liệu ra
Gồm \(t\) dòng, dòng thứ \(i\) ghi YES nếu \(n_i\) có thể viết thành tích của hai số trong dãy Fibonacci, ngược lại ghi NO.
Ràng buộc
- \(1\le t\le 10\)
- \(0\le n_i\le 10^9\)
Subtask
- Subtask 1 (30%): \(0\le n_i\le 10^5\)
- Subtask 2 (30%): \(0\le n_i\le 10^7\)
- Subtask 3 (40%): không có ràng buộc thêm
Sample Input 1
5
5
4
12
11
10
Sample Output 1
YES
YES
NO
NO
YES
Giải thích
Với \(n=5\), ta có \(5=1\times 5\), trong đó \(1\) và \(5\) đều là số Fibonacci nên kết quả là YES.
Với \(n=4\), ta có \(4=2\times 2\), trong đó \(2\) là số Fibonacci nên kết quả là YES.
Với \(n=12\), không thể viết \(12\) thành tích của hai số Fibonacci nên kết quả là NO.
Với \(n=11\), không thể viết \(11\) thành tích của hai số Fibonacci nên kết quả là NO.
Với \(n=10\), ta có \(10=2\times 5\), trong đó \(2\) và \(5\) đều là số Fibonacci nên kết quả là YES.