TITO2 - Tính tổng 2 (OLP Không Chuyên 2014)

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 ≤ 10⁹)
Dữ liệu xuất: Một số nguyên nhất là phần dư của S chia cho 10⁹+7, trong đó S là tổng cần tìm

Ví dụ

• input
  0.3 2.89
  output
  5

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 ≤ 10⁹

^{Nộp bài}

Lần 1:

Bài này thuộc dạng toán học

Cách làm bình thường chỉ ăn được nửa điểm kia thôi!

Code: http://ideone.com/qpBnHG

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

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