trang chủ / đề bài / bp_tst_24_f

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

  • 1≤ai≤m, với 1≤i≤n;
  • ai+1 chia hết cho ai, với 1≤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 3·108. 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 n,m.

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 998244353.

Ràng buộc

  • 1≤n,m≤3·108.

Subtasks

Bài chấm theo từng test.

  • 5% số test ứng với 5% số điểm: n,m≤2·104.
  • 10% số test khác ứng với 10% số điểm: n,m≤2·105.
  • 10% số test khác ứng với 10% số điểm: n,m≤2·106.
  • 75% số test còn lại ứng với 75% số điểm: n,m≤3·108.

Ví dụ

Input Output Giải thích
3 5 16 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).
1 7 7 Với n=1, mỗi dãy chỉ có một phần tử, có 7 dãy (1),(2),…,(7).

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0