Up the Strip
Contest: Codeforces Round 740 (Div. 1, based on VK Cup 2021 - Final (Engine))
Difficulty rating: 1900
Tags: brute force, dp, math, number theory, two pointers

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

Input format:
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.

Output format:
Print the number of ways to move the token from cell $$$n$$$ to cell $$$1$$$, modulo $$$m$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 128.0 MB

Note:
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.

Example input:
3 998244353

Example output:
5

Example input:
5 998244353

Example output:
25

Editorial:
This problem was inspired by Blogewoosh #4 a long time ago (Blogewoosh #8 when?).
Pretty clearly, we are facing a dynamic programming problem. Let $$$f(x)$$$ be the number of ways to move from cell $$$x$$$ to cell $$$1$$$. Then, $$$f(1) = 1$$$, $$$f(x) = \sum \limits_{y=1}^{x-1} f(x-y) + \sum \limits_{z=2}^{x} f(\lfloor \frac{x}{z} \rfloor)$$$, and $$$f(n)$$$ is the answer to the problem. However, a straightforward implementation has $$$O(n^2)$$$ time complexity and is too slow.
Let's look at the main formula for $$$f(x)$$$ again: $$$f(x) = \sum \limits_{y=1}^{x-1} f(x-y) + \sum \limits_{z=2}^{x} f(\lfloor \frac{x}{z} \rfloor)$$$.
The first sum, $$$\sum \limits_{y=1}^{x-1} f(x-y)$$$, is easy to optimize: just maintain the sum of $$$f_1 \ldots f_{x-1}$$$ and recalculate it by adding $$$f(x)$$$. This takes just $$$O(1)$$$ time per cell.
For the second sum, $$$\sum \limits_{z=2}^{x} f(\lfloor \frac{x}{z} \rfloor)$$$, note that $$$\lfloor \frac{x}{z} \rfloor$$$ can take at most $$$O(\sqrt{x})$$$ different values over $$$z \in [2; x]$$$. We can handle this sum as follows:
• Find the sum over all $$$z < \sqrt{x}$$$ directly.
• We only need to consider $$$z \ge \sqrt{x}$$$ now. For any such value, $$$\lfloor \frac{x}{z} \rfloor \le \sqrt{x}$$$. Let's loop over a cell $$$c \le \sqrt{x}$$$, for how many different values of $$$z$$$ it's true that $$$c = \lfloor \frac{x}{z} \rfloor$$$? By definition of the floor function, $$$c \le \frac{x}{z} < c+1$$$. Solving this inequality, we get $$$z \in [\lfloor \frac{x}{c+1} \rfloor + 1; \lfloor \frac{x}{c} \rfloor]$$$. The length of this segment gives us the coefficient of $$$f(c)$$$ in the sum.
This gives us an $$$O(n \sqrt{n})$$$ solution which is enough for the subtask in Division 2.
To get a faster solution, let $$$S(x)$$$ denote the multiset of cells where we can go to from cell $$$x$$$ (this multiset contains $$$2x-2$$$ values). How is $$$S(x+1)$$$ different from $$$S(x)$$$?
• $$$S(x+1)$$$ contains an extra occurrence of $$$x$$$ because we can subtract $$$1$$$ from $$$x+1$$$.
• $$$S(x+1)$$$ contains an extra occurrence of $$$1$$$ because we can divide $$$x+1$$$ by $$$x+1$$$.
• For each $$$i > 1$$$ that is a divisor of $$$x+1$$$, $$$S(x+1)$$$ contains an occurrence of $$$i$$$ that replaces an occurrence of $$$i-1$$$.
We don't need to maintain $$$S(x)$$$ itself, but we can maintain the sum of $$$f(i)$$$ over all $$$i \in S(x)$$$ and recalculate this sum as we go from $$$x$$$ to $$$x+1$$$. The total number of changes to $$$S$$$ is limited by the total number of divisors of all numbers from $$$1$$$ to $$$n$$$, that is, $$$\frac{n}{1} + \frac{n}{2} + \ldots + \frac{n}{n} = O(n \log n)$$$.
However, if implemented directly, we need to quickly find the divisors of each $$$x$$$, and we can only afford $$$O(n)$$$ memory due to the memory limit. We can achieve that by preparing a sieve of Eratosthenes, factorizing $$$x$$$ and generating all its divisors.
A better way is do it the reverse way: once we find $$$f(c)$$$ for some $$$c$$$, let's traverse $$$x = 2c, 3c, \ldots$$$ and add $$$f(c) - f(c-1)$$$ to $$$f(x)$$$. This way the time complexity stays $$$O(n \log n)$$$ and the memory complexity is $$$O(n)$$$.