Hướng dẫn cho TLEoj Contest #08 - Fibonacci lũy thừa
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask 1: a^b\le 88
Tutorial
Với a^b\le 88 thì ta có thể nhận thấy F_{a^b}\le 10^{18}. Vì vậy ta có thể lưu mảng F_1\rightarrow F_{88} rồi sau đó xuất kết quả dựa vào 2 mod.
Subtask 2: a^b\le 10^{18},c\le 88
Tutorial
Với giới hạn này, ta dễ dàng nhận thấy có thể sử dụng nhân ma trận. Độ phức tạp: O(log(a^b))
Subtask 3: c\le 88
Tutorial
Ta nhận thấy dãy F_1\ mod\ F_c, F_2\ mod\ F_c, F_3\ mod\ F_c,\dots sẽ lặp lại với một chu kỳ nào đó. Với giới hạn c nhỏ, ta có thể tự tìm chu kỳ của dãy rồi sau đó xuất kết quả dựa vào chu kỳ.
Subtask 4, 5, 6: Không có ràng buộc gì thêm
Tutorial
Ta sẽ chia bài toán này làm 2 phần: Chứng minh công thức và giải bài toán:
Công thức 1
Công thức
F_a≡F_{b-1}^{\lfloor \frac{a-1}b\rfloor}\times F_{[(a-1)\ mod\ b]+1}\ (mod\ F_b) (≡ là phép đồng dư)
Chứng minh
Ta chứng minh bằng quy nạp, ta có:
- F_1≡F_1,F_2≡F_2,\dots,F_{n-1}≡F_{n-1},F_n≡F_n≡0\ (mod\ F_n)
- F_{n+1}≡F_{n-1}+F_n≡F_{n-1}\times F_1
- F_{n+2}≡F_n+F_{n+1}≡F_{n-1}\times F_2
- F_{n+3}≡F_{n+1}+F_{n+2}≡F_{n-1}\times F_1+F_{n-1}\times F_2≡F_{n-1}\times F_3
- \dots
- F_{2n-1}≡F_{n-1}\times F_{n-1}≡F_{n-1}^2
- F_{2n}≡F_{n-1}\times F_n≡0
- F_{2n+1}≡F_{2n-1}+F_{2n}≡F_{n-1}^2\times F_1
- F_{2n+2}≡F_{2n}+F_{2n+1}≡F_{n-1}^2\times F_2
- \dots
Thực hiện quy nạp liên tục như vậy, ta suy ra điều cần chứng minh
Công thức 2
Công thức
Tính F_{x-1}^2\ mod\ F_x\ (x\ge 3)
Chứng minh
Ta tiếp tục chứng minh bằng quy nạp, giả sử ta xét tính F_{x-1}^2-F_x\times F_{x-2}\ (x\ge 3). Ta có:
- Với x=3, ta có F_2^2-F_1\times F_3=1^2-1\times 2=-1
- Với x=4, ta có F_3^2-F_2\times F_4=2^2-1\times 3=1
- Với x\ge 5, ta có F_{x-1}^2-F_x\times F_{x-2}=F_{x-1}(F_{x-1}-F_{x-2})-F_{x-2}^2=(F_{x-2}+F_{x-3})\times F_{x-3}-F_{x-2}^2=F_{x-3}^2+F_{x-2}(F_{x-3}-F_{x-2})=F_{x-3}^2-F_{x-2}\times F_{x-4}
- Với x lẻ, ta có F_{x-1}^2-F_x\times F_{x-2}=F_2^2-F_1\times F_3=-1
- Với x chẵn, ta có F_{x-1}^2-F_x\times F_{x-2}=F_3^2-F_2\times F_4=1
Từ công thức trên, ta có:
- Với x lẻ, F_{x-1}^2≡F_{x-1}^2-F_x\times F_{x-2}≡-1\ (mod\ F_x)
- Với x chẵn, F_{x-1}^2≡F_{x-1}^2-F_x\times F_{x-2}≡1\ (mod\ F_x)
Kết luận
Từ công thức trên, ta có thể nhận thấy F_{x-1}^4≡1\ (mod\ F_x), hay nói cách khác, theo công thức 1, ta suy ra được F_a≡F_{b-1}^{\lfloor \frac{a-1}b\rfloor\ mod\ 4}\times F_{[(a-1)\ mod\ b]+1}\ (mod\ F_b), hoặc là F_a≡F_{a\ mod\ 4b}\ (mod\ F_b)
Công thức 3
Công thức
Tính F_a\ mod\ F_b (a rất lớn)
Sai lầm
Ta có thể suy ra được công thức F_a≡F_{b-1}^{\lfloor \frac{a-1}b\rfloor\ mod\ 4}\times F_{[(a-1)\ mod\ b]+1}\ (mod\ F_b), nhưng đó sẽ là một sai lầm lớn vì khi tính nhân như trên ta không thể khử được mod\ F_b (đặc biệt với trường hợp F_{b-1} lớn)
Nhận xét
Ta có ý tưởng xét 4 trường hợp (gọi x=a\ mod\ 4b):
- 1\le x\le b: Đơn giản chỉ là tính F_x
- 2b+1\le x\le 3b: Từ nhận xét F_{b-1}^2≡F_{2b-1}≡1 với b chẵn hoặc F_{b-1}^2≡F_{2b-1}≡-1 với b lẻ, ta chỉ cần tính F_{x\ mod\ b} và xét tính chẵn lẻ của b để suy ra kết quả
- 3b+1\le x\le 4b: Ta biết F_{4b}\ mod\ F_b và F_{4b-1}\ mod\ F_b lần lượt là 0 và 1, từ đó ta dễ dàng tính quy nạp như sau:
- F_{4b}≡0
- F_{4b-1}≡1≡F_1
- F_{4b-2}≡F_{4b}-F_{4b-1}≡-F_1≡-F_2
- F_{4b-3}≡F_{4b-1}-F_{4b-2}≡F_1+F_2≡F_3
- F_{4b-4}≡F_{4b-2}-F_{4b-3}≡-F_2-F_3≡-F_4
- \dots
Thực hiện quy nạp liên tục đến F_{3n+1} ta có công thức như sau:
- Với 4b-x chẵn: F_x≡-F_{4b-x}
- Với 4b-x lẻ: F_x≡F_{4b-x}
Tất nhiên vì các giá trị này nhỏ, ta dễ dàng nhận thấy có thể khử được mod\ F_b, vấn đề được giải quyết
- b+1\le x\le 2b: Tương tự với trường hợp 3, nhưng chú ý tính âm dương của F_{2b-1}
Kết luận
Dựa vào các công thức trên, ta có ý tưởng chính như sau:
- Tính a^b\ mod\ 4c, giải quyết bằng lũy thừa nhị phân
- Xét 4 trường hợp như trong công thức 3. Để giải quyết tất cả trường hợp này, ta sử dụng nhân ma trận. Độ phức tạp: O(log(a^b\ mod\ 4c))
Chú ý với trường hợp c\le 2 thì nên xét riêng.
Bình luận