Tìm số dư khi chia số Fibonaci cho 1000000

[whis]

Mô tả Bài toán:

Số Fibonacci bắt đầu từ số 0 và 1. Số Fibonacci khởi đầu sẽ là 0, và số Fibonacci đầu tiên sẽ là 1. Kể từ đó, số thứ hai sẽ là tổng của hai số Fibonacci trước đó.

Công thức của Fn = Fn-1 + Fn-2 (n> = 2).

Các số Fibonacci đến n = 16 như sau: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987.

Viết chương trình tìm ra số Fibonacci thứ n. Tuy nhiên, bởi vì con số đó có thể rất lớn, cho nên chúng ta sẽ in ra kết quả sau khi chia lấy dư với 1,000,000.

Các bạn có thể tham khảo 1001 số Fibonacci đầu tiên trong lúc debug chương trình của các bạn tại http://www.fullbooks.com/The-first-1001-Fibonacci-Numbers.html.

Mô tả Input:

• Dòng đầu tiên sẽ là số nguyên dương n với giá trị nhỏ hơn hoặc bằng 1,000,000,000,000,000,000.

Mô tả Output:

• Kết quả của số Fibonacci thứ n sau khi chia lấy dư với 1,000,000.

Minh họa	Input	Output
1	0	0
2	1	1
3	2	1
4	597	881602

trong hình là đoạn code em làm. nhưng em nộp bài thì nó bị lỗi time limit exceed . mọi người có thể giúp em được không ạ

[rogp10]

1. N này chỉ có long long mới chịu nổi.
2. Dùng ma trận max speed

[whis]

là dùng cách nhân ma trận phải không ạ

[rogp10]

Lũy thừa một ma trận.

Dễ thấy:
[1 1 | 1 0] x [F_k | F_k-1] = [F_k+1 | F_k]
nên đặt M₁ = [1 1 | 1 0]
vậy theo nguyên lí quy nạp và định nghĩa phép nhân, M_n := [F_n+1 F_n | F_n F_n-1] = M₁ⁿ

Theo đó ta gọi m₁ := vector cột bên phải của M₁, có luôn M_k x m_k’ = m_k+k’.

Ta tính theo kiểu bình phương - nhân, nói chung cứ đặt a, b, c, d mà tính chứ ko cần lập mảng gì nó có liên quan đến biểu diễn nhị phân của số mũ.