r*******g
发帖数: 1335 | 1 Zenefits OA 2
uneaten leaves
http://www.careercup.com/question?id=5288825291014144
网上很多地方说用inclusion-exclusion principle，但是实际很难做，除非你用了很
多space把所有的集合都保存在一起。
我发觉他的难点在于：
假设K=3对应三个蛾子分别是A,B,C。被lcm(A,B)整除的数，有可能也被C整除，所以，
除非一个个把数列出来，否则似乎很难真正用什么inclusion-exclusion。但是你既然
列出来了，那不是已经就求解出来了吗，原题就只是叫你找出被A或B或C整除的即可，
何必管这个数被几个数整除呢？
我是用lcm解答的，先算出所有蛾子的lcm，然后计算1-lcm中可以被蛾子吃掉的叶子，
假设为M。也就是说，1-lcm中有M个叶子被吃掉，lcm+1到2*lcm中有M个叶子被吃掉，一
直上去就行了。
但是，计算1-lcm倍蛾子吃掉的叶子，本身就比较慢，而且这里也没法用什么inclusion
-exclusion，原因同上。我是很初级方法算的。
所以问题就是，网上说的inclusion-exclusion到底是啥？怎么用
thanks | a***u
发帖数: 383 | 2 不知道你想怎么算1-lcm被吃掉的叶子。比较初级的方法是弄个set把1-lcm放进去，然
后一个虫子一个虫子的过，每个虫子吃了哪个叶子就删哪个叶子，这样太慢了。容斥原
理就是A吃了几个叶子，B吃了几个叶子，C吃了几片叶子然后加加减减就好。好处是只
用算吃了几片叶子，而不用看到底吃了哪几片叶子 | x*******9
发帖数: 138 | |
|
