Up the Strip
题意翻译
### 题面描述
你有一张 $ 1 \times n $ 的纸带,由 $ n $ 个格子组成。初始有一个点在 $ n $ 号格子(即左数第 $ n $ 个)中。
假设现在这个点在 $ x\ (x > 1) $ 号格子,每次你可以对这个点进行如下操作中的一种:
1. 减法。选择一个 $ [1, x - 1] $ 中的正整数 $ y $,将点移动到 $ x - y $ 号格子中。
2. 除法。选择一个 $ [2, x] $ 中的正整数 $ z $,将点移动到 $ \lfloor \frac{x}{z} \rfloor $ 号格子中。
当点在 $ 1 $ 号格子中时无法移动,操作结束。
求将点从 $ n $ 号格子移到 $ 1 $ 号格子的方案数,答案对给定的模数取模。
两个方案不同当且仅当有一步选择的操作或选择的数不同。例如:$ x = 5 $ 时,选择操作 $ 1 $ 且 $ y = 4 $,或选择操作 $ 2 $ 且 $ z = 3\ 或\ 4\ 或\ 5 $ 时,点都将被移到 $ 1 $ 号格子,但这些都是不同的方案。
### 输入格式
一行两个数,纸带长度 $ n $ 和模数 $ m $。
### 输出格式
一行一个数,表示答案对 $ m $ 取模的结果。
### 数据范围
$ 2 \leqslant n \leqslant 4 \cdot 10^6, 10^8 < m < 10^9, m $ 是质数。
题目描述
Note that the memory limit in this problem is lower than in others.
You have a vertical strip with $ n $ cells, numbered consecutively from $ 1 $ to $ n $ from top to bottom.
You also have a token that is initially placed in cell $ n $ . You will move the token up until it arrives at cell $ 1 $ .
Let the token be in cell $ x > 1 $ at some moment. One shift of the token can have either of the following kinds:
- Subtraction: you choose an integer $ y $ between $ 1 $ and $ x-1 $ , inclusive, and move the token from cell $ x $ to cell $ x - y $ .
- Floored division: you choose an integer $ z $ between $ 2 $ and $ x $ , inclusive, and move the token from cell $ x $ to cell $ \lfloor \frac{x}{z} \rfloor $ ( $ x $ divided by $ z $ rounded down).
Find the number of ways to move the token from cell $ n $ to cell $ 1 $ using one or more shifts, and print it modulo $ m $ . Note that if there are several ways to move the token from one cell to another in one shift, all these ways are considered distinct (check example explanation for a better understanding).
输入输出格式
输入格式
The only line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 4 \cdot 10^6 $ ; $ 10^8 < m < 10^9 $ ; $ m $ is a prime number) — the length of the strip and the modulo.
输出格式
Print the number of ways to move the token from cell $ n $ to cell $ 1 $ , modulo $ m $ .
输入输出样例
输入样例 #1
3 998244353
输出样例 #1
5
输入样例 #2
5 998244353
输出样例 #2
25
输入样例 #3
42 998244353
输出样例 #3
793019428
输入样例 #4
787788 100000007
输出样例 #4
94810539
说明
In the first test, there are three ways to move the token from cell $ 3 $ to cell $ 1 $ in one shift: using subtraction of $ y = 2 $ , or using division by $ z = 2 $ or $ z = 3 $ .
There are also two ways to move the token from cell $ 3 $ to cell $ 1 $ via cell $ 2 $ : first subtract $ y = 1 $ , and then either subtract $ y = 1 $ again or divide by $ z = 2 $ .
Therefore, there are five ways in total.