Viết chương trình đọc vào hai số thực dương a và b và tính tổng bình phương tất cả các số
nguyên không nhỏ hơn a và không lớn hơn b.
Dữ liệu nhập: Gồm một dòng chứa hai số thực dương a, b (0 < a ≤ b ≤ 109)
Dữ liệu xuất: Một số nguyên nhất là phần dư của S chia cho 109+7, trong đó S là tổng cần tìm
nguyên không nhỏ hơn a và không lớn hơn b.
Dữ liệu nhập: Gồm một dòng chứa hai số thực dương a, b (0 < a ≤ b ≤ 109)
Dữ liệu xuất: Một số nguyên nhất là phần dư của S chia cho 109+7, trong đó S là tổng cần tìm
Ví dụ
- input0.3 2.89output5
Sẽ có 10 bộ test, tỉ lệ tương ứng với kì thi OLP
- 5 bộ test đầu có 0 < a ≤ b ≤ 1000
- 5 bộ test sau có 0 < a ≤ b ≤ 109
Lần 1:
Bài này thuộc dạng toán học
Lần 2: copied
Sau khi search thì thấy có công thức tính tổng bình phương từ 1 đến n: n(n+1)(2n+1)/6
Sau khi search thì thấy có công thức tính tổng bình phương từ 1 đến n: n(n+1)(2n+1)/6
Kết hợp với xem bài giải của các bạn ta có: Đặt F(n) = n(n+1)(2n+1)/6
Như vậy kết quả bài toán sẽ là F(b) - F(a) % M
Nhưng thế này chỉ đúng thêm 1 test thứ 6 và sai ở test thứ 7. Do vẫn dính phải việc tràn số do số quá lớn.
Code: http://ideone.com/AAOC77
Lần 3: copied
Mặt khác, ta thấy: n(n+1) luôn chia hết cho 2 (vì 1 trong 2 số phải là số chẵn).
Do đó F(n) = [n*(n+1)/2]*(2*n+1)/3 : Tức là vừa nhân, ta vừa chia để giảm kết quả đến nhỏ nhất có thể, nếu nhân 2 lần liên tiếp rồi mới chia kết quả có thể tràn số.
Kết hợp cả công thức tính phần dư nữa ta được:
F(n) = n*(n+1)/2%M*(2*n+1)/3
Tức là ta vừa chia vừa lấy phần dư để kết quả nhỏ nhất có thể.
Và một chú ý khi lấy phần dư nữa là kết quả có thể F(b) < F(a) do đó phải tính đến trường hợp đấy.
Code: http://ideone.com/3gyNmz
Bài học: Có thể không nghĩ ra được cách giải đúng, nhưng với cách giải hiện tại phải tìm mọi cách để tối ưu bài toán, ví dụ ở trên ngta làm thêm từng bước nhỏ để giảm nhỏ tối thiểu kết quả của phép nhân.
#namlunoy
Không có nhận xét nào:
Đăng nhận xét