Chia quà (Bản khó)
Xem PDF
Điểm:
900
Thời gian:
5.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Minh có \(N\) món quà và muốn chia cho \(M\) bạn.
Minh muốn sau khi chia:
- Mỗi bạn nhận được số quà bằng nhau.
- Mỗi bạn nhận được ít nhất \(K\) món quà.
- Tất cả các món quà đều phải được chia hết, không được để thừa.
Nếu số quà hiện tại chưa đủ hoặc không thể chia đều, Minh có thể mua thêm một số món quà. Hãy tính số món quà ít nhất Minh cần mua thêm để có thể chia quà thỏa mãn các điều kiện trên.
Input
- Dòng đầu tiên chứa số nguyên \(T\) — số bộ test.
- Mỗi dòng trong \(T\) dòng tiếp theo chứa ba số nguyên \(N, M, K\).
Output
- In ra \(T\) dòng, mỗi dòng là số món quà ít nhất cần mua thêm tương ứng với một bộ test.
Constraints
- \(1 \le T \le 10^5\)
- \(1 \le N \le 10^{18}\)
- \(1 \le M, K \le 10^9\)
Example
Test 1
Input
5
20 5 3
20 5 5
30 8 4
100 6 10
1 100 1Output
0
5
2
2
99Note
- Ở test thứ nhất: Minh có \(20\) món quà, chia cho \(5\) bạn thì mỗi bạn nhận được \(20 / 5 = 4\) món. Mỗi bạn nhận được \(4\) món, lớn hơn hoặc bằng \(3\), nên không cần mua thêm.
- Ở test thứ hai: Mỗi bạn cần nhận ít nhất \(5\) món quà, có \(5\) bạn nên cần ít nhất \(5 \cdot 5 = 25\) món. Minh đang có \(20\) món, nên cần mua thêm \(25 - 20 = 5\) món.
- Ở test thứ ba: Cần ít nhất \(8 \cdot 4 = 32\) món. Minh có \(30\) món, nên cần mua thêm \(2\) món.
- Ở test thứ tư: Minh có \(100\) món quà. Mỗi bạn cần ít nhất \(10\) món, với \(6\) bạn thì cần ít nhất \(60\) món, điều này đã đủ. Tuy nhiên, \(100\) không chia hết cho \(6\). Số nhỏ nhất lớn hơn hoặc bằng \(100\) và chia hết cho \(6\) là \(102\). Vậy Minh cần mua thêm \(102 - 100 = 2\) món.
- Ở test thứ năm: Có \(100\) bạn, mỗi bạn cần ít nhất \(1\) món, nên cần ít nhất \(100\) món quà. Minh đang có \(1\) món, nên cần mua thêm \(100 - 1 = 99\) món.
Bình luận (1)