QOJ.ac

QOJ

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓

#16267. 好数组

统计

最近 Vasya 学习了整除。受到这一神圣知识的启发,他决定进一步研究满足某些整除条件的正整数数组。更具体地说,Vasya 称一个数组 $a = \{a_1, a_2, \dots, a_n\}$ 是“好”的,当且仅当对于每个 $i$($1 \le i \le n - 1$),$a_i$ 都能被 $a_{i+1}$ 整除。请帮助他计算长度为 $n$ 且由不大于 $c$ 的正整数组成的好数组的数量。

输入格式

输入仅包含一行,其中有两个整数 $n$ 和 $c$($1 \le n, c \le 5 \cdot 10^7$),分别表示数组的长度和允许的最大值。

输出格式

输出一个整数,表示由不大于 $c$ 的正整数组成的长度为 $n$ 的好数组的总数。由于这个数可能很大,请输出它模 $998\,244\,353$ 的余数。

样例

输入样例 1

3 3

输出样例 1

7

输入样例 2

2 6

输出样例 2

14

子任务

本题的测试集由 7 个测试组组成。只有当你的程序通过该组中的所有测试以及所有依赖组中的测试时,你才能获得该组的分数。“离线评测”(Offline-evaluation)意味着你不会立即获得该组的反馈,只有在比赛结束后才能看到结果。

子任务 分值 附加限制 $n$ 附加限制 $c$ 依赖子任务 说明
0 0 样例
1 15 $n \le 10$ $c \le 10$ 0
2 14 $n \le 1000$ $c \le 1000$ 0, 1
3 12 $n \le 5000$ $c \le 5000$ 0 – 2
4 16 $n \le 100\,000$ $c \le 100\,000$ 0 – 3
5 14 $n \le 10^6$ $c \le 10^6$ 0 – 4
6 15 $n \le 10^7$ $c \le 10^7$ 0 – 5
7 14 0 – 6 离线评测

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.