Biểu thức bậc ba
Đề bài
Cho các số nguyên $a, b, c, d$ và $x$. Hãy tính giá trị của biểu thức
$$P = a \cdot x^3 + b \cdot x^2 + c \cdot x + d.$$
Dữ liệu vào: Một dòng gồm năm số nguyên dương $a, b, c, d, x$ cách nhau bởi dấu cách.
Kết quả: In ra giá trị của $P$.
Giới hạn: $1 \le a, b, c, d, x \le 10^4$.
Subtask:
- Subtask 1 (40% số điểm): $a, b, c, d, x \le 100$.
- Subtask 2 (60% số điểm): không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.
79 85 66 66 61182518761 1 1 1 14Giải thích:
- Ví dụ 1: $79 \cdot 61^3 + 85 \cdot 61^2$ $+ 66 \cdot 61 + 66$ $= 79 \cdot 226\,981$ $+ 85 \cdot 3\,721$ $+ 4\,026 + 66$ $= 17\,931\,499$ $+ 316\,285$ $+ 4\,026 + 66$ $= 18\,251\,876$.
- Ví dụ 2: $1 \cdot 1^3 + 1 \cdot 1^2 + 1 \cdot 1 + 1 = 4$.
Nguồn: phỏng theo bài "BIỂU THỨC" – vinhdinhcoder.net.
Lời mở đầu
Lại một bài "chỉ cần gõ công thức", nhưng lần này công thức có lũy thừa bậc ba, nên có tới hai cái bẫy: số quá lớn so với int, và hàm pow quen thuộc trả về số thực. Mình sẽ chấm thật 5 cách viết – từ cách sai tới cách đúng – để các bạn thấy mỗi lỗi mất bao nhiêu điểm, rồi giới thiệu thêm sơ đồ Horner: cách tính đa thức gọn và nhanh mà dân lập trình rất hay dùng.
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 chính thức có gì?
Bộ test có 20 test, mỗi test là một dòng 5 số. Mình đã kiểm tra: test 1–8 thoả điều kiện subtask 1 (mọi số $\le 100$), test 9–20 là subtask 2.
| Nhóm | Test | Số lớn nhất trong input | $P$ nhỏ nhất | $P$ lớn nhất | Số test $P >$ INT_MAX | Số test $P > 2^{53}$ |
|---|---|---|---|---|---|---|
| Subtask 1 | 1–8 | 100 | 4 | 101.010.100 | 0 | 0 |
| Subtask 2 | 9–20 | 10.000 | 18.831.415.171 | 10.001.000.100.010.000 | 12 | 3 |
- Subtask 1: $P \le 100 \cdot 100^3$ $+ 100 \cdot 100^2$ $+ 100 \cdot 100$ $+ 100$ $= 101\,010\,100$ $\approx 10^8$ – vừa kiểu
int. - Subtask 2: cả 12 test đều có $P$ vượt
INT_MAX; $P$ có thể lên tới $10^4 \cdot (10^4)^3 + \dots \approx 10^{16}$, và có 3 test $P$ vượt cả $2^{53} \approx 9 \cdot 10^{15}$ (ngưỡng mà kiểudoublecòn lưu chính xác mọi số nguyên).
Kết quả chạy thật của các cách bên dưới theo từng subtask:
| Subtask | Test | Cách 1int | Cách 2pow | Cách 3pow + ép kiểu | Cách 4long long | Cách 5 Horner |
|---|---|---|---|---|---|---|
| Subtask 1 (40%) | 1–8 | 8/8 | 3/8 | 8/8 | 8/8 | 8/8 |
| Subtask 2 (60%) | 9–20 | 0/12 | 0/12 | 11/12 | 12/12 | 12/12 |
Ý tưởngMỗi số hạng lớn cỡ nào?
Trước khi code, mình ước lượng độ lớn của từng phần trong biểu thức với $a, b, c, d, x \le 10^4$:
- $x^3 \le 10^{12}$, nên $a \cdot x^3 \le 10^{16}$ – số hạng lớn nhất.
- $b \cdot x^2 \le 10^{12}$, $c \cdot x \le 10^8$, $d \le 10^4$.
- Tổng $P \le 10^{16} + 10^{12} + 10^8 + 10^4$ $\approx 1{,}0001 \cdot 10^{16}$: quá lớn cho
int($\approx 2{,}1 \cdot 10^9$), nhưng nằm gọn tronglong long($\approx 9{,}2 \cdot 10^{18}$).
Em nhập 5 số rồi bấm Tiếp để xem từng số hạng được tính ra sao. Mỗi thanh dài theo số chữ số của giá trị: vạch cam là giới hạn int, vạch xanh là $2^{53}$ (giới hạn chính xác của double), cả thanh là giới hạn long long:
Cách 1Dùng int – đúng subtask 1
Với subtask 1 mọi giá trị trung gian đều $\le 10^8$ nên chạy đúng. Sang subtask 2, ngay phép a*x*x*x đã vượt INT_MAX → tràn số, in ra số rác (có khi âm). Em thử ví dụ 1 1 1 1 2000 trong khung chạy tay: $x^3 = 8 \cdot 10^9$ đã tràn ngay ở phép nhân thứ ba.
Kết quả chạy thật: Bản C++ đúng 8/20 test, sai test 9–20, chạy lâu nhất 0.003s. Đúng trọn subtask 1, sai toàn bộ 12 test subtask 2 → được 40% điểm.
Cách 2Dùng pow – sai cả ví dụ
Nhiều bạn quen viết lũy thừa bằng hàm pow(x, 3):
pow(x, 3) có kiểu double, nên a * pow(x, 3) và cả biểu thức cũng thành double. Khi in bằng cout, số thực mặc định chỉ hiện 6 chữ số có nghĩa và chuyển sang dạng khoa học nếu số lớn: ví dụ 1 in ra 1.82519e+07 thay vì 18251876.Kết quả chạy thật: Bản C++ đúng 3/20 test, sai test 1, 3, 6–20, chạy lâu nhất 0.003s. Chỉ đúng 3 test có $P$ nhỏ hơn 1 triệu (test 2, 4–5) – còn tệ hơn cách 1.
Cách 3pow + ép kiểu long long – suýt đúng
Sửa cách 2 bằng cách ép kết quả về long long để in ra dạng số nguyên:
Lần này kết quả đúng gần hết, nhưng vẫn sai một test. Lý do: double chỉ có 53 bit để lưu phần định trị, nên nó lưu chính xác mọi số nguyên đến $2^{53} = 9\,007\,199\,254\,740\,992$. Lớn hơn mức đó, double chỉ lưu được các số chẵn (rồi bội của 4, của 8...). Một tổng $P \approx 10^{16}$ mà là số lẻ sẽ bị làm tròn thành số chẵn bên cạnh → lệch 1 đơn vị.
Ví dụ (không phải test ẩn) 9999 1 1 1 10000: đáp án đúng là $9\,999\,000\,100\,010\,001$ (số lẻ, lớn hơn $2^{53}$), nhưng cách 3 in ra 9999000100010000. Em thử ngay trong khung chạy tay bên dưới.
Kết quả chạy thật: Bản C++ đúng 19/20 test, sai test 11, chạy lâu nhất 0.004s. Test sai có đáp án là số lẻ cỡ $10^{16}$, đúng như phân tích. Bài học: tính toán số nguyên thì đừng đi đường vòng qua số thực.
Cách 4Dùng long long – full điểm
Khai báo cả 5 biến là long long rồi viết công thức bằng các phép nhân số nguyên. Mọi giá trị trung gian đều $\le 1{,}0001 \cdot 10^{16}$, rất xa giới hạn $9{,}2 \cdot 10^{18}$.
- Phải khai báo các biến là
long long(hoặc ít nhấtavàx). Nếu đểintrồi chỉ đổiPthànhlong longthìa*x*x*xvẫn tính bằngintvà tràn trước khi gán. - Thứ tự
a*x*x*x=((a*x)*x)*x: giá trị trung gian lớn nhất là chính $a \cdot x^3 \le 10^{16}$, an toàn.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.017s. Full điểm.
Cách 5Sơ đồ Horner – gọn và ít phép nhân
Đặt $x$ làm nhân tử chung liên tiếp:
$$P = a x^3 + b x^2 + c x + d = \big((a \cdot x + b) \cdot x + c\big) \cdot x + d.$$
Ta chỉ cần lặp lại đúng một thao tác "nhân với $x$ rồi cộng hệ số tiếp theo": bắt đầu từ $P = a$, rồi $P = P \cdot x + b$, $P = P \cdot x + c$, $P = P \cdot x + d$. Chỉ 3 phép nhân thay vì 6, và với đa thức bậc $n$ thì chỉ cần $n$ phép nhân – đây là cách các thư viện tính giá trị đa thức trong thực tế.
Thử với ví dụ 1 ($a = 79$, $x = 61$): $P = 79 \to 79 \cdot 61 + 85$ $= 4\,904 \to 4\,904 \cdot 61 + 66$ $= 299\,210 \to 299\,210 \cdot 61$ $+ 66$ $= 18\,251\,876$. ✔
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.019s. Full điểm.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
1. int | C++ | 8/20 | 0.003s | Tràn số toàn bộ subtask 2 |
2. pow, in double | C++ | 3/20 | 0.003s | In dạng 1.82519e+07 khi P từ 1 triệu trở lên |
3. pow + ép long long | C++ | 19/20 | 0.004s | double mất chính xác khi P > 2^53 |
4. long long | C++ | 20/20 | 0.003s | Full điểm |
| Python | 20/20 | 0.017s | Full điểm | |
| 5. Horner | C++ | 20/20 | 0.003s | Full điểm |
| Python | 20/20 | 0.019s | Full điểm |
long long); (2) không dùng pow cho lũy thừa số nguyên – tự nhân x*x*x hoặc dùng Horner; (3) double chỉ chính xác tuyệt đối với số nguyên tới $2^{53} \approx 9 \cdot 10^{15}$.
Nhận xét
Đăng nhận xét