30/09/2018, 21:36
Tính số fibonacci thứ n modulo cho m
Mình đang làm bài tập này và có chút thắc mắc:
Cho n và m là 2 số tương đối lớn, hãy tính kết quả của số fibonacci thứ n mod cho m (Fn mod m).
Nếu n là một số cực kỳ lớn, thì việc tìm ra được số đó là rất khó khăn, nên cách tốt nhất là không tìm nó. Có một cách đơn giản hơn là dùng dãy số Pisano:
Đoạn phía trên ví dụ cho n = 2015 và m = 3 nên độ dài chuỗi Pisano của m là 8. Nhưng nếu m là một số nào đó khoảng vài nghìn thì có cách nào tính được độ dài dãy Pisano của m không?
Bài liên quan
Fn =(Fn-1+Fn-2) % m
Dùng QHD hoặc nhân ma trận có thể tính dc
Nói chung nếu (m,n) < 1018 thì dùng nhân ma trận là dc bài trên.