一只毛毛虫会吃掉所有距离为“跳跃步长”
j
的倍数的叶子,因此如果只有一只毛毛虫,那么每只毛毛虫将吃掉
floor(n/j)
个叶子。
现在你需要找出哪些叶子被多次计数。例如,如果你为第一只毛毛虫计算了所有能被2整除的叶子,则不必再为第二只毛毛虫计算任何叶子,因为它每隔4个跳跃步长才会吃掉一片叶子。
对于两个毛毛虫,这些重复计数的数字是它们的
最小公倍数的倍数,这样的数字有
floor(n/lcm(j,j'))
个。
请注意,对于三个以上的跳跃步长,如果按照上述方法计算,可能会重复删除某些叶子:以28为例,它会被跳跃步长为7的毛毛虫吃掉,但是却为两只其他毛毛虫都计数(因为28 % 4 == 28 % 2 == 0),因此需要加回被多次删除的倍数:
floor(n/lcm(j,j',j"))
。
你可以看到这里有一个模式,它是
容斥原理。通用公式如下:
![inclusion-exclusion formula](https://istack.dev59.com/ajnXy.webp)
令Aj表示一只毛毛虫独自吃掉的跳跃步长为j的叶子集合。然后对于多只毛毛虫跳跃步长的集合J,A
J是所有这些毛毛虫都会吃掉的叶子集合。
![AJ is the intersection of the Aj where j is in J](https://istack.dev59.com/jQDHX.webp)
同时,定义集合的最小公倍数为集合中所有元素的最小公倍数,我们可以写成
lcm(J)
。
[n]在包含-排除公式中是考虑的毛毛虫跳跃的集合,因此在您的情况下为[2,4,7]
,我们会遍历它的所有子集。|J|是子集的大小,|AJ|是J中每个毛毛虫可能吃掉的叶子数,所以我们得到|AJ| = floor(n/lcm(J))
。
现在您有2的次幂的总和,因为那是只毛毛虫子集的数量。请注意,您可以通过保存最小公倍数而不是从头重新计算来节省一些时间。
我把写实际代码 "作为练习"留给你们,因为有些人喜欢说:基本上就是迭代子集并计算最小公倍数,然后将其全部放入上面的总和中。
这将使您获得所消耗的总叶片数。从这里获取未被吃掉的叶子非常简单。
如果我们在一个小例子上做一下(以便能够检查),其中0为地面,1..24
为叶子,[2,3,4]
为毛毛虫跳跃步骤。
唯一幸存的叶子将是{1、5、7、11、13、17、19、23}:删除所有偶数和所有可被3整除的数字。也就是说,我们希望答案为8。
- 第一轮:大小为1的子集。
- 毛毛虫
j=2
单独吃12片叶子
- 毛毛虫
j=3
单独吃8片叶子
- 毛毛虫
j=4
单独吃6片叶子
- 第二轮:大小为2的子集。
- 毛毛虫
j=2
和j=3
都想吃24/6 = 4片叶子: {6, 12, 18, 24}
- 毛毛虫
j=3
和j=4
都想吃24/12 = 2片叶子: {12, 24}
- 毛毛虫
j=4
和j=2
都想吃24/4 = 6片叶子: 所有被4
吃的都是2
的目标
- 第三轮:大小为3的子集:所有毛毛虫一起
- 他们都想吃24/lcm(2,3,4)=24/12 = 2片叶子: {12,24}.
- 最终轮:已经吃掉12 + 8 + 6 - 4 - 2 - 6 + 2 = 26 - 12 + 2 = 16片叶子
所以还剩下24 - 16 = 8片叶子。
* 当然,这是最坏情况。希望您迭代逐渐增加的子集,并且只要子集J的最小公倍数大于n
,您就可以忽略所有的J的超集。特别地,如果所有大小为k
的子集的lcm都大于n,则可以停止迭代。