蓝桥杯-取余 | 小彦同学的摸鱼空间

type

status

date

slug

summary

📝 题目

这道题如果一开始就使用暴力嵌套的话，必定会超时。后来盯着题目看了好久，还是没有找到思路。于是只能去看看其他高手的题解，研究了很长时间,看了个似懂非懂。因此，这里记录一下研究出来的思路。

假设我想要对10以下的所有数进行对1取模，那么最后会有多少个数的余数为0呢？答案是10个，即10/1。

接下来，假设我想要对10以下的所有数进行对2取模，那么最后会有多少个数的余数为0呢？答案是5个，而且余数为1的个数也为5个,即10/2。

假设我想要对10以下的所有数进行对3取模，那么最后会有多少个数的余数为0，多少个数的余数为1呢？答案是余数为0的数有3个，即10/3；余数为1的数有4个,即10/3⇒3+1=4

现在关键的问题来了，

假设我想要对10以下的所有数进行对6取模，那么最后会有多少个数的余数为0，多少个数的余数为1,多少个数的余数为2,多少个数的余数为3,多少个数的余数为4,,多少个数的余数为5呢？

答案是余数为0的数有1个，即10/6；余数为1的数有2个,即10/6⇒1+1=2

余数为2的数有2个,即10/6⇒1+1=2,余数为3的数有2个,即10/6⇒1+1=2

余数为4的数有2个,即10/6⇒1+1=2,余数为5的数有1个,即10/6=1

为什么余数为0和余数为4不用加一，是因为10%6⇒4，所以只在1,2,3,4里面加

根据以上的描述，我们可以研究出一些规律。按照这个规律，我们只需要对b循环i次，即可得出[a,b]数对所有的余数。

总结：当A/i时，所得的结果即为所有小于a的数对i取模的值。如果A%i不为0，则还需在[1,A%i]的范围内的余数数量上加1。

然后为了进一步优化复杂度，首先用一个数组来存储余数的数量，下标则为余数，然后采用差分数组进一步优化

假设初始的差分数组为 diff = [0, 0, 0, 0, 0]，对应初始的 arr 数组。

要将 arr 的索引 1 到 3 的元素每个增加 5，我们只需要在差分数组上做以下操作：

现在差分数组变为 diff = [0, 5, 0, 0, -5]。

要还原原始数组 arr，我们只需要累加差分数组的元素：

所以最终数组 arr 成为 [0, 5, 5, 5, 0]，与使用普通方法得到的结果相同。

但差分数组的优势在于更新操作的复杂度。不管区间有多大，更新操作（修改 diff[L] 和 diff[R+1]）的时间复杂度都是 O(1)，这对于处理大量区间更新操作非常有效。

结合起来就是题解代了

主要在于取模运算的运用

💡

有关题目或文章的问题，欢迎您在底部评论区留言，一起交流~