Doraemon và cuộc phiêu lưu ở hòn đảo kho báu (Bản khó)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
thenymphsofdelphi
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cảm thấy quá mệt mỏi với việc nghỉ dịch Covid-19 ở nhà, Doraemon rủ Nobita và những người bạn đi phiêu lưu ở hòn đảo kho báu ở Mỹ cách đây 1500 năm. Sau khi đến đảo, vì quá mệt mỏi sau chuyến hành trình dài, mọi người quyết định nghỉ chân một lúc. Tại đây, Doraemon chợt nhớ ra việc học hành bết bát của Nobita nên đã đố Nobita một câu hỏi để ôn lại các thuật toán khủng như Suffix Array, Treap, Palindrome Tree, etc…

Doraemon cho Nobita 1 chiếc hộp đặc biệt biết cứ bỏ \(M\) quả chuối vào chiếc hộp này thì tất cả quả chuối sẽ biến mất. Sau đó Doraemon cho Nobita 2 số \(L\) và \(R\) và bắt Nobita phải chọn 2 số \(i\) và \(j\) \((i < j)\) trong đoạn \(L\) và \(R\). Sau khi chọn Nobita sẽ có được tổng số chuối là \(i \times j\). Tiếp theo, cậu sẽ phải liên tục bỏ \(M\) quả chuối vào thùng đến khi số chuối còn lại ít hơn \(M\). Vì Nobita là 1 cậu bé “ngốc nghếch” nên cậu muốn biết được số lượng chuối còn lại ít nhất sau khi bỏ vào thùng.

Input

  • Một dòng duy nhất, gồm ba số lần lượt là \(L, R, M\) \((1 \leq L < R \leq 10^9, 1 \leq M \leq 2000)\).

Output

  • Một dòng duy nhất, là kết quả của bài toán.

Scoring

  • Ở bản dễ, \(1 \leq L < R \leq 2000\).
  • Ở bản khó, \(1 \leq L < R \leq 10^9\).

Example

Test 1

Input 
4 7 13
Output 
2
Note

Nếu chọn \(i = 4\) và \(j = 7\) thì số quả chuối còn lại là \((4 \times 7) - 2 \times 13 = 2\) quả.

Bình luận