VM 09 Bài 05 - Nuga chia kẹo
Xem dạng PDF
Gửi bài giải
Điểm:
1,38 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Tết Trung Thu sắp đến và chị Nuga đã mua rất nhiều kẹo để chia cho các em của mình. Tổng số Nuga có ~M~ chiếc kẹo và cần chia hết cho ~N~ em. Để cho tiện, ta đánh số các em từ ~1~ đến ~N~.
Nuga biết rằng em thứ ~i~ chỉ vui khi nhận được ít nhất ~A_{i}~ cái kẹo. Nhưng bố mẹ của em ấy cũng không muốn con mình ăn quá ~B_{i}~ chiếc (để tránh sâu răng). Như thế, Nuga phải chia cho em thứ ~i~ số kẹo là ~X_{i}~ thỏa mãn ~A_{i} \leq X_{i} \leq B_{i}~.
Bạn hãy giúp Nuga tính xem có bao nhiêu cách chia ~M~ chiếc kẹo cho ~N~ em để thỏa mãn tất cả các yêu cầu trên.
Input
- Dòng đầu ghi ~2~ số nguyên ~M~, ~N~.
- Dòng thứ hai gồm ~N~ số nguyên ~A_{1}~, ~A_{2}~, ..., ~A_{n}~.
- Dòng thứ ba gồm ~N~ số nguyên ~B_{1}~, ~B_{2}~, ..., ~B_{n}~.
Output
- Một dòng duy nhất chứa số cách chia thỏa mãn.
Giới hạn
- Trong ~30\%~ tổng số test, ~1 \leq N \leq 5~ và ~0 \leq A_{i} \leq B_{i} \leq M \leq 20~.
- Trong các test còn lại, ~1 \leq N \leq 16~ và ~0 \leq A_{i} \leq B_{i} \leq M \leq 10^{9}~.
Sample Input
6 3
0 0 0
3 2 4
Sample Output
9
Bình luận
cho em hỏi bài này có cần dùng bignum để ac không ạ ?