CodeForces 1558B Up the Strip

有 $n(2\le n\le 4\cdot {10}^6)$ 个节点，编号 $1\sim n$，你一开始在节点 $n$，想要到节点 $1$。假设你现在在节点 $x$，你可以进行以下两种操作：

1. 选择一个正整数 $y\in [1,x-1]$，并移动到节点 $x-y$。
2. 选择一个正整数 $z\in [2,x]$，并移动到节点 $\lfloor \frac{x}{z}\rfloor$。

求有多少种方案到达节点 $1$，只要有一次选择的 $x$ 或 $z$ 不同就算方案不同。答案对 $m$ 取模，其中 $m\in ({10}^8,{10}^9)$ 且 $m$ 是素数。

令 $f_i$ 表示 $n=i$ 时的答案，我们有：

前一部分表示用减法，后一部分表示用除法。

考虑优化，第一部分直接前缀和，我们直接考虑第二部分。一种很直接的优化是将小于 $\sqrt{i}$ 的 $d$ 直接拿出来算，大于 $\sqrt{i}$ 的 $d$ 拿出来算贡献， $f_k$ 能转移到 $f_i$ 的 $d$ 应该满足 ，也即 ，于是 $f_k$ 对 $f_i$ 的贡献应该为 $\lfloor \frac{n}{k}\rfloor -\lfloor \frac{n}{k+1}\rfloor$。这样做复杂度是 $\mathcal{O}(n\sqrt{n})$，过不去，但是如果你打 Div. 2 的话就能过一个 easy 版。

我们考虑换一种方式，考虑 $f_i$ 转移到 $f_{i+1}$，我们比较 $\sum _{d=2}^i{f}_{\lfloor \frac{i}{d}\rfloor }$ 与 $\sum _{d=2}^{i+1}{f}_{\lfloor \frac{i+1}{d}\rfloor }$，有如下变化：

1. 多了一个 $f_1$，因为 $d$ 可以等于 $i+1$。
2. 对于所有 $d\mid i+1$，$\lfloor \frac{i+1}{d}\rfloor =\lfloor \frac{i}{d}\rfloor +1$，所以 $f_{i+1}$ 比 $f_i$ 多了一个 $f_{\lfloor \frac{i+1}{d}\rfloor }$，少了一个 $f_{\lfloor \frac{i}{d}\rfloor }$。

也就是说：

我们发现对于所有 $i$，总的约数个数为 $\sum _{i=1}^n\frac{n}{i}=\mathcal{O}(n\log n)$。其余转移为 $\mathcal{O}(n)$，故总复杂度为 $\mathcal{O}(n\log n)$。

考虑实现，在每次计算出 $f_i$ 的时候，将所有的 $f_{ki}$ 都加上 $f_i-f_{i-1}$，这样空间复杂度就是 $\mathcal{O}(n)$。

const int maxn = 4000005;

int n, mod;

void add(int& x, int y) {
    x += y;
    if (x >= mod) {
        x -= mod;
    } else if (x < 0) {
        x += mod;
    }
}

int f[maxn];

int main() {
    read(n), read(mod);
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        int tmp = f[i - 1] << 1 | 1;
        if (tmp >= mod) {
            tmp -= mod;
        }
        add(f[i], tmp);
        if (i == 2) {
            f[i] = 2;
        }
        for (int j = i << 1; j <= n; j += i) {
            add(f[j], f[i]);
            add(f[j], -f[i - 1]);
        }
    }
    writeln(f[n]);
    return 0;
}