Chữ số (Tin học trẻ toàn quốc 2023 – Vòng khu vực miền Trung – Bảng B, C2)
Đề bài
Cho hai số nguyên dương $a, b$. Dãy $fib$ được xây dựng giống dãy Fibonacci nhưng hai số đầu tùy ý:
- $fib(1) = a$, $fib(2) = b$;
- $fib(n)$ $= fib(n - 1) + fib(n - 2)$ với mọi $n \ge 3$.
Yêu cầu: cho $a, b, L, R$ ($a, b \le 10^{18}$, $L \le R \le 10^{18}$), tìm chữ số hàng đơn vị của tổng
$S = fib(L) + fib(L + 1)$ $+ \dots + fib(R)$.
Dữ liệu vào:
- Dòng đầu: số nguyên dương $T$ ($T \le 100$) – số bộ dữ liệu.
- $T$ dòng sau, mỗi dòng bốn số nguyên dương $a, b, L, R$.
Kết quả: $T$ dòng, mỗi dòng một chữ số – chữ số cuối của $S$ ứng với bộ dữ liệu đó.
Subtask:
- Subtask 1 (40%): $R \le 10^6$;
- Subtask 2 (30%): $R - L \le 10^6$;
- Subtask 3 (30%): không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.
2
1 1 1 3
1 1 3 34
2Giải thích: với $a = b = 1$ thì $fib(1) = 1$, $fib(2) = 1$, $fib(3) = 2$. Bộ thứ nhất $S = 1 + 1 + 2 = 4$; bộ thứ hai chỉ có một số hạng $S = fib(3) = 2$.
Lời mở đầu
Đây là bài "dễ mà dễ sai" của đề miền Trung: số hạng của dãy lớn khủng khiếp (vượt xa long long chỉ sau vài chục số hạng), $R$ tới $10^{18}$ nên không thể cộng từng số. Mấu chốt là đề chỉ hỏi chữ số cuối, tức là chỉ cần làm việc với các số mod 10. Mình đi 3 bước: cộng thẳng (40 điểm) → nhảy nhanh tới $L$ bằng lũy thừa ma trận (70 điểm) → phát hiện dãy mod 10 tuần hoàn chu kỳ 60 (100 điểm).
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ điểm subtask của đề: 20 test, mỗi test có tới $T = 100$ bộ dữ liệu (test 1 là ví dụ của đề). Có đủ các trường hợp $a, b = 10^{18}$, $L = 1$, $R = 10^{18}$, $L, R$ rơi đúng bội của 60 hoặc lệch 1 so với bội của 60 (để bắt lỗi chỉ số).
| Nhóm | Test | Số bộ $T$ | Tổng số bộ | $R$ lớn nhất | $R - L$ lớn nhất | $a, b$ lớn nhất |
|---|---|---|---|---|---|---|
| Subtask 1 | 1–8 | 2, 5, 10, 100 | 517 | 1.000.000 | 999.999 | 1018 |
| Subtask 2 | 9–14 | 4, 100 | 504 | 1018 | 1.000.000 | 1018 |
| Subtask 3 | 15–20 | 5, 100 | 505 | 1018 | ≈ 1,00·1018 | 1018 |
Kết quả chạy thật các cách bên dưới theo từng subtask (số test đúng / số test của subtask):
| Subtask | Điều kiện | Test | Cách 1 C++ | Cách 1 Python | Cách 2 C++ | Cách 2 Python | Cách 3 C++ | Cách 3 Python |
|---|---|---|---|---|---|---|---|---|
| Subtask 1 (40%) | $R \le 10^6$ | 1–8 | 8/8 | 3/8 | 8/8 | 3/8 | 8/8 | 8/8 |
| Subtask 2 (30%) | $R - L \le 10^6$ | 9–14 | 0/6 | 0/6 | 6/6 | 1/6 | 6/6 | 6/6 |
| Subtask 3 (30%) | không ràng buộc thêm | 15–20 | 0/6 | 0/6 | 0/6 | 0/6 | 6/6 | 6/6 |
Ý tưởngChỉ giữ chữ số cuối và dãy sẽ lặp lại
Nhận xét 1. Chữ số cuối của một tổng chỉ phụ thuộc vào chữ số cuối của các số hạng: $(x + y) \bmod 10$ $= \big((x \bmod 10) + (y \bmod 10)\big) \bmod 10$. Vậy thay vì $fib(n)$ khổng lồ, ta chỉ cần $f(n) = fib(n) \bmod 10$, và $f(n) = (f(n-1) + f(n-2)) \bmod 10$ – các số luôn từ 0 đến 9.
Nhận xét 2 (tuần hoàn). Số hạng tiếp theo chỉ phụ thuộc vào cặp hai số hạng liền trước $(f(n-1), f(n))$. Cặp này chỉ có $10 \times 10 = 100$ khả năng, nên chắc chắn có lúc cặp bị lặp lại, và từ đó dãy lặp lại y hệt. Hơn nữa dãy còn "chạy lùi" được ($f(n-2) = f(n) - f(n-1)$) nên phần lặp bắt đầu ngay từ đầu dãy. Người ta đã biết dãy Fibonacci mod 10 có chu kỳ 60 (gọi là chu kỳ Pisano), và điều này đúng với mọi cặp $a, b$ ban đầu vì $fib(n)$ luôn là tổ hợp $x \cdot a + y \cdot b$ của hai dãy Fibonacci chuẩn.
Nhận xét 3. Gọi $P(n) = f(1) + f(2) + \dots + f(n)$ (mod 10). Khi đó đáp án là $(P(R) - P(L - 1)) \bmod 10$, và nhờ chu kỳ 60:
$P(n) = \lfloor n / 60 \rfloor \cdot P(60)$ $+ P(n \bmod 60) \pmod{10}$.
Em nhập $a, b, L, R$ rồi bấm Tiếp để xem dãy $f$ được lập, chu kỳ 60 hiện ra, và cách tính đáp án chỉ bằng vài phép tra bảng:
Một điều thú vị em sẽ thấy trong widget: $P(60)$ luôn bằng 0 (tổng một chu kỳ chia hết cho 10). Lý do: với dãy kiểu Fibonacci có $fib(1) + \dots + fib(n)$ $= fib(n + 2) - fib(2)$, nên $P(60)$ $= f(62) - f(2)$ $= f(2) - f(2)$ $= 0$. Dù vậy lời giải cuối mình vẫn viết đủ công thức cho dễ hiểu.
Cách 1Cộng thẳng từ 1 tới R (Subtask 1)
Đi lần lượt $i = 1, 2, \dots, R$, giữ hai biến x = f(i), y = f(i + 1) (đã mod 10). Gặp $i \ge L$ thì cộng x vào tổng. Chú ý a % 10 ngay từ đầu vì $a, b$ tới $10^{18}$.
- Không cần mảng: mỗi bước chỉ "trượt" cặp $(x, y) \to (y, x + y)$.
- Mọi phép cộng đều
% 10nên không bao giờ tràn số.
Kết quả chạy thật: Bản C++ đúng 8/20 test, quá thời gian test 9–20 (các test đúng chạy lâu nhất 0.189s) → 40 điểm. Bản Python đúng 3/20 test, quá thời gian test 4–20 (các test đúng chạy lâu nhất 0.212s) – Python cộng tới $10^8$ lần (100 bộ × $R = 10^6$) thì quá chậm, chỉ qua được 3 test nhỏ.
Cách 2Nhảy tới L bằng lũy thừa ma trận (Subtask 1, 2)
Ở subtask 2, $L$ rất lớn nhưng đoạn $[L, R]$ ngắn ($\le 10^6$ số). Phần tốn thời gian của cách 1 là "đi bộ" từ 1 tới $L$. Ta "nhảy" thẳng tới $L$ bằng công thức ma trận quen thuộc của Fibonacci:
$\begin{pmatrix} fib(i+1) \\ fib(i) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{i-1} \begin{pmatrix} fib(2) \\ fib(1) \end{pmatrix}$
Lũy thừa ma trận $2 \times 2$ tính bằng lũy thừa nhanh trong $O(\log L)$ phép nhân (mọi phần tử mod 10). Có $f(L)$ và $f(L+1)$ rồi thì cộng tiếp từ $L$ tới $R$ như cách 1.
luyThua(M, p): nếu bit thấp nhất củaplà 1 thì nhân kết quả vớiM; sau đó bình phươngMvà dịchpsang phải.- Từ $P = M^{L-1}$: $f(L+1)$ $= P_{00} \cdot f(2) + P_{01} \cdot f(1)$ và $f(L) = P_{10} \cdot f(2) + P_{11} \cdot f(1)$.
Kết quả chạy thật: Bản C++ đúng 14/20 test, quá thời gian test 15–20 (các test đúng chạy lâu nhất 0.243s) → 70 điểm. Subtask 3 có $R - L$ gần $10^{18}$ nên vòng cộng vẫn quá chậm. Bản Python đúng 4/20 test, quá thời gian test 4–8, 10–20 (các test đúng chạy lâu nhất 0.143s).
Cách 3Chu kỳ 60 – tổng tiền tố (full)
Làm đúng như phần ý tưởng: lập $f(1..60)$ và tổng tiền tố pre[0..60] (mod 10), rồi $P(n)$ = (số chu kỳ đầy đủ) × pre[60] + pre[n % 60].
du % 10: số chu kỳ $\lfloor n / 60 \rfloor$ có thể tới $1{,}6 \cdot 10^{16}$; lấy mod 10 trước khi nhân cho chắc chắn không tràn.(P(R) - P(L - 1) + 10) % 10: hiệu có thể âm, cộng thêm 10 để về số không âm (trong C++,%của số âm cho kết quả âm).- Khi $L = 1$ thì
P(0) = pre[0] = 0– đúng.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.016s – Python cũng nhẹ nhàng.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Điểm theo subtask |
|---|---|---|---|---|
| 1. Cộng thẳng từ 1 tới R | C++ | 8/20 | 0.189s | 40% |
| Python | 3/20 | 0.212s | 0% | |
| 2. Nhảy tới L bằng lũy thừa ma trận, cộng L..R | C++ | 14/20 | 0.243s | 70% |
| Python | 4/20 | 0.143s | 0% | |
| 3. Chu kỳ 60 (chu kỳ Pisano) | C++ | 20/20 | 0.004s | 100% |
| Python | 20/20 | 0.016s | 100% |