Count the number of beautiful sequences

Revision en2, by bao987, 2025-07-21 12:25:52

Consider a sequence a = a1, a2, ..., an of length n. The sequence a is called beautiful if it satisfies both of the following conditions:

  • For all i from 1 to n, the value of a[i] is between 1 and m, inclusive.

  • For all i from 1 to n — 1, a[i] is a divisor of a[i + 1].

Count how many such beautiful sequences exist.

Since the answer can be very large, output the result modulo 998244353.

Constraints:

1 ≤ n, m ≤ 3 × 10⁸

Time limit: 5s

Sample input:

3 6

Sample output:

20

Could you all please help me? I really appreciate it!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English bao987 2025-07-21 16:27:48 2 Tiny change: 'tput:\n\n20\n\nCould ' -> 'tput:\n\n25\n\nCould '
en4 English bao987 2025-07-21 12:26:29 0 Tiny change: 'om 1 to n — 1, a[i] i' -> 'om 1 to n - 1, a[i] i' (published)
en3 English bao987 2025-07-21 12:26:09 0 Tiny change: 'om 1 to n — 1, a[i] i' -> 'om 1 to n - 1, a[i] i' (saved to drafts)
en2 English bao987 2025-07-21 12:25:52 0 Tiny change: 'om 1 to n — 1, a[i] i' -> 'om 1 to n - 1, a[i] i'
en1 English bao987 2025-07-21 12:20:42 616 Initial revision (published)