Dãy chia hết
Đề bài
Mô tả
Phương Anh đang cùng các bạn trong đội tuyển thi HSG làm một bài toán với đề khá ngắn do Nam đố. Bài toán đó như sau:
Cho hai số nguyên dương . Hãy đếm số dãy gồm phần tử sao cho thỏa mãn tất cả các điều kiện dưới đây:
- , với ;
- chia hết cho , với .
Đề khá ngắn gọn, dễ hiểu, nhưng số được cho trước khá lớn, lên đến . Phương Anh khá bối rối khi gặp bài toán này do ít tiếp xúc với những bài toán dãy chia hết. Huy, một bạn trong đội tuyển thi HSG giải được bài toán này, Huy còn cho biết chỉ cần một chút kiến thức toán "nhỏ" có thể giải được bài này một cách dễ dàng. Nam sau một phút suy nghĩ cũng đồng tình với ý kiến của Huy.
Yêu cầu: Hãy giúp Phương Anh thoát khỏi sự bối rối bằng cách đếm số dãy thỏa mãn tất cả các điều kiện trên.
Dữ liệu vào
Gồm một dòng duy nhất chứa hai số nguyên dương .
Dữ liệu ra
In ra một số nguyên duy nhất là phần dư của kết quả bài toán khi chia cho .
Ràng buộc
- .
Subtasks
Bài chấm theo từng test.
- số test ứng với số điểm: .
- số test khác ứng với số điểm: .
- số test khác ứng với số điểm: .
- số test còn lại ứng với số điểm: .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 | 16 | Một số dãy thỏa mãn là , , , , . |
| 1 7 | 7 | Với , mỗi dãy chỉ có một phần tử, có dãy . |
Bình luận