A. 数一下

题目描述

给定一个正整数 \(N\)，求 \(N\bmod1,N\bmod2,\dots,N\bmod N\) 中有多少个不同的值。

思路

我们对 \(N\bmod i\) 的 \(i\) 进行分类讨论：

• \(i \ge \lceil\frac{N}{2}\rceil\)，那么 \(N\bmod i=N-i\)，所以这部分包含了 \(0\) 到 \(\lfloor\frac{N}{2} \rfloor\)。
• \(i< \lceil\frac{N}{2}\rceil\)，那么 \(N\bmod i < \lceil \frac{N}{2}\rceil-1\le \lfloor\frac{N}{2} \rfloor\)，所以肯定也在该范围内。

综上，有 \(\lfloor \frac{N}{2}\rfloor+1\) 个不同的数。

B. 数两下

题目描述

给定一个数列，求将其分成若干非空子段使得每段 mex 相同的方案数。

思路

可以发现，这些段的 mex 如果要相同，那么只能等于整个数组的 mex。按这个 dp 即可。

时空复杂度均为 \(O(N)\)。