Aug 31

Lucky Number zju 3233 解题报告 不指定

Posted by ringsd at 09:05 | ACM » 组合数学 | 评论(3) | 阅读(2219) | 转自 本站原创 | |
题意:哇他是这个猥琐男喜欢M mm,而M mm似乎想要故意为难他一下,所以她给了哇他是一串BLN和一串BUN,以及一个给定Luck number的定义:一个数是Lcuk number当且仅当这个数可以被整除BLN中的任意一个而不整除BUN中的任意一个。
现在M mm给了哇他是一个区间[low, high],让哇他是在这个区间里面找出一个数来,如果这个数满足Luck number的定义,那么M mm就嫁个他。
现在哇他是想要知道这个区间里面有多少个满足Luck number定义的数。

看完题后的第一感觉就是容斥原理,具体容斥原理的资料可以找本组合数学的书看看。

不过一开始对于“不整除BUN中的任意一个”这句话有点疑惑,其实这句话的方面就是“去掉整除BUN中所有数的数”这样我们就很好理解了,我们把Luck number的定义看作是两个条件:
1.求出所有能够整除BLN的数
2.求出所有能够整除BLN但是又不整除所有BUN的数(不整除所有BUN的数,其实就是不整除BUN的最小公倍数)
我们要求的Luck number实际上就是:满足条件1的数减去满足条件2的数

根据容斥原理求解某个数的因子个数,我们可以很轻松的求解出某个区间里面所有满足条件1的数,那么条件2我们怎么求呢?其实条件2我们同样是运用容斥原理来求解,我们只需要将BLN中所有的数的组合乘以BUN中的最小公倍数运用一次容斥原理就可以求解出满足条件2的数了,求解出来的两个答案相减,over!

这个题目WA了N次,问题就出在我构造的使用容斥原理求解因子个数的程序的预处理上,一开始我写程序的时候包含有一个排序操作预处理数组的,后来修改程序过程中删除了,但是我在构造数据的时候一直按照从小到大的循序构造的,因此一直没有找出错误来……
内文分页: [1] [2]
Tags: , , , , ,
dionello Homepage
2010/07/13 19:24
感谢这片的好信息......
Jacobs Homepage
2010/07/12 19:38
为感谢您的网站,我总是在这里找到很多有趣的
lee Homepage
2009/09/02 12:32
grin完全不懂的人路过。貌似Chrome下页面有点变形。
261762586 回复于 2009/09/03 00:20
额 看来模版还是没有通过chrome的内核呀 呵呵!!
怎么会完全不懂呢?
你也是学计算机的哈!
哈哈!
分页: 1/1 第一页 1 最后页