Solutions of Fibonacci 3

Select solution language

chithanhnguyen Created at 2 likes

Ký hiệu $F_n$ là số Fibonacci thứ $n$ được định nghĩa là: $F_0 = 0; F_1 = 1; F_n = F_{n - 1} + F_{n - 2} \ (n \geq 2)$. Ta có nhận xét: $f_n = F_{n - 1}\times x + F_n\times y \ (\text{*}) \ (n \geq 2)$. Nhận xét này có thể dễ dàng chứng minh bằng quy nạp theo $n$, chứng minh chi tiết xin dành lại cho bạn đọc. Cố định $n$, ta quy về đếm số bộ $(x, y)$ để $f_n = k$. Vì dãy Fibonacci tăng rất nhanh nên số giá trị phải xét là rất ít chỉ khoảng $45$ số ($F_{45} = 1134903170$) Khi cố định $n$, ta cần đếm số bộ $(x, y)$ nguyên dương sao cho: $$ F_{n - 1}\times x + F_n\times y = k $$ trong đó $F_{n - 1}, F_n$ là hằng số nên bài toán quy về đếm số nghiệm nguyên dương của phương trình Diophantine (bạn đọc có thể test code tại [đây](https://lqdoj.edu.vn/problem/diophantine)) Độ phức tạp là $O(45 \times \log k)$.

minhpnk2 Created at 0 likes

## Nhận xét ### Nhận xét 1 - Ta thấy rằng chỉ có tầm $30$ số fibonacci $\le 10^9$ mà thôi. - Tạm thời gọi $\theta_i$ với định nghĩa như sau: - $\theta_0 = \theta_1 = 1 \ \forall i \in [0, 1]$ - $\theta_i = \theta_{i - 1} + \theta_{i - 2} \ \forall i \in [2, \infty]$ ### Nhận xét 2 Khi ta nháp thử các biểu thức có thể xảy ra, ta thấy một điều như sau * $f_0 = x$ * $f_1 = y$ * $f_2 = f_1 + f_0 = x + y = \theta_1 x + \theta_0 y$ * $f_3 = f_2 + f_1 = x + y + x = \theta_2 x + \theta_1 y$ * $f_4 = f_3 + f_2 = \theta_3 x + \theta_2 y$ * $\ldots$ * $f_i = \theta_{i - 1}x + \theta_{i - 2}y$ Ta thay từng cái $f_i$ bằng $k$ Nhiệm vụ của ta lúc này là tìm số lượng nghiệm **nguyên dương** thoả mãn một trong $30$ phương trình trên Ta thấy nó giống với [phương trình Diophantine](https://viblo.asia/p/phuong-trinh-diophantine-tuyen-tinh-018J2NqqJYK) nên ta sẽ dùng thuật toán [Eculid mở rộng](https://wiki.vnoi.info/algo/algebra/euclid) để giải quyết chúng