CF1561D1.Up the Strip (simplified version)

本题与下一题的区别仅在于 $n$ 的约束条件。

注意，本题的内存限制比其他题目更低。

你有一个由 $n$ 个格子组成的竖直条带，这些格子从上到下依次编号为 $1$ 到 $n$。

你还有一个棋子，初始时放在第 $n$ 个格子上。你需要不断地将棋子向上移动，直到它到达第 $1$ 个格子。

假设某一时刻棋子位于第 $x$ 个格子（$x > 1$）。每次移动棋子可以有以下两种方式之一：

• 减法操作：你选择一个整数 $y$，满足 $1 \le y \le x-1$，然后将棋子从第 $x$ 个格子移动到第 $x-y$ 个格子。
• 向下取整除法操作：你选择一个整数 $z$，满足 $2 \le z \le x$，然后将棋子从第 $x$ 个格子移动到第 $\lfloor \frac{x}{z} \rfloor$ 个格子（即 $x$ 除以 $z$ 向下取整）。

请你计算，将棋子从第 $n$ 个格子移动到第 $1$ 个格子的所有不同方案数（每次至少要移动一次），并将结果对 $m$ 取模后输出。注意，如果存在多种方式能在一次移动中将棋子从一个格子移动到另一个格子，则这些方式都视为不同的方案（参见样例解释以加深理解）。

一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$10^8 < m < 10^9$，$m$ 是质数），分别表示条带的长度和取模的数。

输出一个整数，表示将棋子从第 $n$ 个格子移动到第 $1$ 个格子的方案数，对 $m$ 取模。

在第一个测试样例中，有三种方式可以在一次移动中将棋子从第 $3$ 个格子移动到第 $1$ 个格子：减去 $y=2$，或者除以 $z=2$ 或 $z=3$。

还有两种方式可以通过第 $2$ 个格子间接到达第 $1$ 个格子：先减去 $y=1$ 到达第 $2$ 个格子，然后再减去 $y=1$ 或除以 $z=2$ 到达第 $1$ 个格子。

因此，总共有五种方案。

由 ChatGPT 4.1 翻译