Số học (Thuật toán Euclid, Bao hàm - Loại trừ, Tổ hợp)

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 2000, 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

4 7 13 

2

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

4 7 13 

2

Em nhận được một món quà từ ông tiên. Ông ban cho em hộp gồm vô hạn viên bi xanh. Tuy nhiên khi sử dụng bi để chơi trò chơi thì cần dùng đúng \(X\) viên bi xanh. Có 2 thao tác được sử dụng là:

• Thao tác 1: Lấy \(A\) viên bi xanh từ trong hộp ra.
• Thao tác 2: Bỏ \(B\) viên bi xanh từ ngoài vào hộp.

Yêu cầu duy nhất ông tiên đưa ra là em phải dùng ít thao tác nhất để lấy được đúng \(X\) viên bi xanh thì chiếc hộp sẽ thuộc về em mãi mãi.

Ví dụ em cần lấy ra 7 viên bi xanh (\(X = 7\)), \(A = 3, B = 8\) thì số thao tác ít nhất phải dùng là 6 trong đó dùng 5 lần thao tác 1, 1 lần thao tác 2.

Input

• Gồm một dòng chứa 3 số nguyên dương \(A, B, X\) (\(A \le 10^{18}, B \le 10^{18}, X \le 10^{18}\)).

Output

• Ghi ra một số nguyên dương duy nhất là tổng số thao tác ít nhất cần phải thực hiện. Nếu không có cách thực hiện để lấy được đúng \(X\) bi xanh thì đưa ra -1.

Example

3 8 7

6

Ông Lionheart - thị trưởng của Bilaspur, có một kế hoạch cho cư dân của mình. Ông ta muốn giới thiệu một hệ thống tiền tệ chỉ gồm 2 loại tiền mệnh giá \(a\) đồng và \(b\) đồng. Nhưng có một vấn đề rắc rối là có những khoản tiền không thể chi trả bằng cách chỉ sử dụng 2 loại tiền này. Trong những trường hợp đó, công dân sẽ phải chọn thanh toán kỹ thuật số.

Cho \(n\) khoản tiền, bạn hãy cho biết có bao nhiêu khoản tiền có thể thanh toán được bằng cách sử dụng các loại tiền trên và còn bao nhiêu khoản tiền phải được thanh toán bằng kỹ thuật số. Biết rằng thị trưởng đã cung cấp không giới hạn các loại tiền này.

Input

• Dòng đầu tiên chứa 3 số nguyên \(n, a, b\) (\(1 \le n, a, b \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(c_i\), mô tả \(n\) khoản tiền cần thanh toán (\(1 \le c_i \le 10^5\)).

Output

• Ghi ra một dòng chứa 2 số nguyên tương ứng là số khoản tiền có thể thanh toán bằng 2 loại tiền mệnh giá \(a\) đồng, \(b\) đồng và số khoản tiền phải thanh toán bằng kỹ thuật số.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n, a, b, c_i \le 10^2.\)
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le n, a, b, c_i \le 10^3.\)
• Subtask \(3\) (\(40\%\) số điểm): Như ràng buộc gốc.

Example

5 4 6
16 20 36 22 15

4 1

7 7 5
7 25 14 27 45 34 41

7 0

Có \(n\) chiếc kẹo, có bao nhiêu cách chia kẹo bất kỳ cho \(k\) bạn, mà có thể có bạn không nhận được kẹo?

Dữ liệu đầu vào

• Gồm hai số \(n\) và \(k\) \((k \leq n)\)

Định dạng đầu ra

• In ra đáp án chia lấy dư cho \(10^9+7\)

Điểm số

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000\)
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^6\)

Ví dụ

5 3

21

Có \(n\) chiếc kẹo, có bao nhiêu cách chia kẹo bất kỳ cho \(k\) bạn, mà bạn nào cũng được nhận kẹo?

Dữ liệu đầu vào

• Gồm hai số \(n\) và \(k\) \((k \leq n)\)

Định dạng đầu ra

• In ra đáp án chia lấy dư cho \(10^9+7\)

Điểm số

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000\)
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^6\)

Ví dụ

5 3

6

Xét biểu thức sau: \((x + a)^n\) (với \(a,n\) là số được cho).

Yêu cầu: Khai triển biểu thức trên, tính hệ số bậc \(k\)?

Input

• Một dòng chứa ba số nguyên \(a,n,k\) (\(0 \le a \le 10^9; 1 \le n \le 2 \times 10^5; 0 \le k \le n\)).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán, do kết quả có thể rất lớn, bạn cần đưa ra kết quả chia lấy phần dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(a = 1, n \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 10\).
• Subtask \(3\) (\(25\%\) số điểm): \(a = 1\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

1 2 1

2

Cho \(n\) số tự nhiên \(a_1, a_2, ..., a_n\). Hãy xác định xem có bao nhiêu số \(x\) trong đoạn \([l, r]\) mà \(x\) không chia hết cho số \(a_i\) nào cả.

Input

• Dòng đầu tiên chứa 3 số nguyên dương \(n, l, r \ (1 \leq n \leq 18)\)
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

• In ra một số nguyên là đáp số bài toán

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \leq l \leq r \leq 10^6\)
• Subtask \(2\) (\(70\%\) số điểm): \(1 \leq l \leq r \leq 10^{18}\)

Example

3 10 20
3 4 5 

5