hdu 1796 How many integers can you find (容斥原理)

hdu1796
题意:给出n(<=2^31)以及m(<=10)个元素组成的无重复元素集合,集合元素0<=a[i]<=20,问有多少个小于n的数能至少被集合中的一个元素整除。

思路:容斥,找到能被一个元素的,被两个元素的…加加减减。
一个元素的最小公倍数定义成自己,然后多个元素的就两个两个算…

一个坑点是,a[i]有0,而一个数除以0没有意义。。。所以读入的时候处理下。。。把0删掉(个人觉得这个坑点毫无技术含量。。。。0不能作为除数这种事情呵呵呵)  并且如果只有一个数且为0,那么删掉后集合就为空了,特判输出0.

 

另一个坑点是,别看每个数都很小。。但是求多个数的最小公倍数的时候会爆int…

虽然最后结果没有爆,但是中间量会爆掉,要开long long 

 

20160305update:也写个递归版本的,好简洁有木有。

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz