Chọn ĐTQG Bình Phước 2024 - Dãy chia hết

Xem dạng PDF

Gửi bài giải

Điểm: 90,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

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 ~n, m~. Hãy đếm số dãy ~A~ gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~ sao cho thỏa mãn tất cả các điều kiện dưới đây:

  • ~1 \le a_i \le m~, với ~1 \le i \le n~;

  • ~a_{i+1}~ chia hết cho ~a_i~, với ~1 \le i < n~.

Đề khá ngắn gọn, dễ hiểu, nhưng số ~n, m~ được cho trước khá lớn, lên đến ~2 \cdot 10^8~. 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.

Input

Gồm một dòng duy nhất chứa hai số nguyên dương ~n, m~.

Output

Một số nguyên duy nhất là phần dư của kết quả bài toán khi chia cho ~998244353~.

Scoring

Subtask Điểm Ràng buộc
1 ~5\%~ ~n, m \le 2 \cdot 10^4~
2 ~10\%~ ~n, m \le 2 \cdot 10^5~
3 ~10\%~ ~n, m \le 2 \cdot 10^6~
4 ~75\%~ ~n, m \le 3 \cdot 10^8~

Sample Input 1

3 5

Sample Output 1

16

Notes

Một số dãy thỏa mãn là:

  • ~(1, 1, 2)~;

  • ~(3, 3, 3)~;

  • ~(1, 5, 5)~;

  • ~(2, 4, 4)~;

  • ~(1, 2, 4)~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.