Về dãy Fibonacci. Cái này này theo mình thì không dễ

[KhoaTran (Trần Ngọc Khoa)]

Đề bài: Viết chương trình nhập vào 2 số n và m. Hãy tính F(n)%m. Với F(n) là số Fibinacci thứ n.
Áp dụng chương trình của bạn để tính với trường hợp n = 999999999 và m = 100.

(Mình thi rồi nha, nên không có vụ hỏi bài tập ở đây, chỉ là để thảo luận đối với đề bài mang tính “giải trí” cao này thôi)

---

Một số ý kiến:

• Dãy Fibonacci với phần tử thứ 100 là khổng lồ rồi.
• Việc áp dụng BigNum là khá phức tạp và mất thời gian.
• Thay vì tính F(n) thì tính một vài số cuối của F(n) rồi chia lấy dư cho m có cho kết quả chính xác?

---

Hãy chia sẻ ý tưởng và code của bạn để mọi người cùng test. Hoặc có thể chia sẻ kết quả nếu bạn ngại chia sẻ code.

[minhthai (mt)]

Bài này nếu là mình thì sẽ dùng ma trận . Độ phức tạp ~~ log(n)
p/s: bài này hình như có hỏi ở đây hồi trước rồi thì phải

[chichi]

lưu dãy fibo[1] = fibo[2] = 1 , fibo(n) = (fibo(n-1)+fibo(n-2)) mod m

[tntxtnt]

xài công thức ma trận
F_i+j = F_i+1F_j+1 - F_i-1F_j-1
F_i+j+1 = F_i+1F_j+1 + F_iF_j

lấy của F_n % m để tính ra F_2n % m cho kết quả chính xác:

giả sử
a = q₁m + r₁
b = q₂m + r₂
suy ra
a (mod m) = r₁ (mod m)
b (mod m) = r₂ (mod m)
suy ra
(ab) (mod m) = (r₁r₂) (mod m)
(a+b) (mod m) = (r₁+r₂) (mod m)
(a-b) (mod m) = (r₁-r₂+m) (mod m)
với phép trừ thì có thể r₁-r₂ cho số âm, nên ta chỉ cần cộng thêm m là được.

Với ví dụ n = 100, ta biểu diễn 100 dưới dạng số nhị phân:
100 = (1100100)₂
như vậy F₁₀₀ = F_64+32+4

với bộ đôi F₁ và F₂ khởi điểm, tính:
F₂ và F₃
F₄ và F₅
F₈ và F₉
F₁₆ và F₁₇
F₃₂ và F₃₃
F₆₄ và F₆₅
(bằng công thức ma trận trên với i = j)
rồi kết hợp F₆₄ với F₃₂ và F₄ cho ra F₁₀₀. Nhớ lấy mod m hết.