数论记录

lizihan250 · 2025-11-28 20:41:58 · 个人记录

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

CF2045B ICPC Square

难度：*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})。

CF1749D Counting Arrays

难度：*1900

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

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

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