30/09/2018, 21:55
Giải bài toán với chu kì Pisano
Đây là bài toán em đang gặp trong khóa học mong mọi người giúp đỡ
Input: Nhập n ( <= n <= 10^18) và m ( 2 <= m <= 10^5)
Output: là số fibonacii F[n] chia lấy dư với m;
Theo hướng dẫn thì người ta dùng dãy số pisano để tính (vì số fibonancii có thể lên rất lớn) nhưng em vẫn k hiểu quy luật để tìm ra dãy số đấy Mọi người có thể giúp em được không ạ?
Trên diễn đàn cũng có 1 bài viết như thế này rồi nhưng câu trả lời không đúng theo cách này
Bài liên quan
Dùng nhân ma trận ý.
Bắt đầu mỗi chu kì là 0 và kế tiếp là 1, bạn dùng cái này để cắt chuỗi chu kì. Ta cũng có 1 quy luật khi tính con số tiếp theo của chuỗi tương tự fibonacci: fn = f(n-1) + f(n-2) đó là : fn mod k ={ [ f(n-1) mod k ] + [ f(n-2) mod k ] } mod k ; nói cho dễ hiểu thì lấy 2 số trc trong chuỗi cộng lại rồi modulo cho số k (trong bài là m).
ví dụ f15 mod 3 nó bằng 2+2 mod 3.
Sau khi giải quyết dc đô dài chuỗi rồi thì cái còn lại coi như đơn giản rồi.
+không liên quan: bạn học khóa gì vậy ?
Chu kì pisano m thường lớn hơn m, và phức tạp hơn nhiều so với nhân ma trận. Trừ khi n cực lớn cỡ vài trăm ngàn chữ số thì lúc đó việc tìm chu kì pisano mới hiệu quả