数论记录

被神秘数论/计数题区分了，决定加训数学。

难度：*2000

题目大意：给定 $n,d,s$，从 $s$ 出发，每次跳到其一个与其差不超过 $d$ 的不超过 $n$ 的数。求跳跃终点最大值。

这题有 2000？

首先显然只能跳到 $s$ 的倍数。对 $n,d,s$ 全部除以 $s$。

考虑最后一步。假设最后一步从 $x$ 跳到 $y$，显然，$y - x \ge x$，所以只要最后一步能跳，前面就一定能跳。于是问题转化为找出不超过 $n$ 的与自身真因子差不超过 $d$ 的最大的数。

如果 $2d \le n$，那么显然答案为 $2n$。否则，一定能取到不超过 $n$ 抵达最大偶数。因此只需要在 $n$ 是奇数的时候判断能不能取 $n$，暴力分解即可。时间复杂度 $O(\sqrt{n})$。

难度：*1900

题目大意：对于一个数组，定义一次删除操作是选择一个 $i$ 使得 $a_i$ 与 $i$ 互质，并删除 $a_i$。定义一个数组是模糊的当且仅当其有多种将其删空的方式。问长度不超过 $n$ 且元素不超过 $m$ 的数组中有几个是模糊的。

显然，任何数组都可以不断删去 $a_1$ 以删空。所以，如果 $a_i$ 与一个不超过 $i$ 且不小于 $2$ 的数互质的话，就可以先不断删 $a_1$，使得其对其那个数，然后把它删去，从而找到第二种删除方式。因此，一个数组是模糊的，当且仅当存在一个 $a_i$，满足其与一个不大于 $i$ 的数互质。

正难则反，考虑计算非模糊数组的数量，即对于任意 $a_i$，其与任意不大于 $i$ 的数互质，相当于其能被任意不大于 $i$ 的质数整除。预处理所有的质数，递推计算即可。