AC » Archive » pe problem 268

pe problem 268

十二月 15th, 2009 › Project Euler › ben1222 ›

求10^16内的正整数中,100以内的不同质因数个数最少有4个的数的个数

下面是我的解题过程:

100以内的质数好像是25个…
首先想到的当然是容斥原理…
但是怎么做呢…

题目要求100以内不同质因数个数最少有4个的情况…
看起来挺多的…
于是想计算它的反面…
100以内不同质因数个数最多有3个的情况
看起来挺少的…
最后得到结果之后才发现两者其实没有差太多

具体怎么算呢…
如果写个函数,使得它能告诉我100以内的质因数只能为某几个的情况下,有多少个满足要求的数
这样枚举一下100以内0~3个质因数的所有组合就行了

容斥原理就能算,虽然25个质数有点多…但也就2^25的复杂度…不过100以内0~3个质因数的所有组合的数量乘上去就不小了…
跑了一个半小时终于出了结果…
不过还好答案正确了

貌似有更快的方法…也是用容斥原理…
但貌似用了组合数…
似乎能在1秒内完成…
可惜没法静下心来慢慢理解…
搞acm时切题养成坏习惯…只要过了就万事大吉了- -|||

评论暂缺

Comments RSS TrackBack Identifier URI

No comments. Be the first.

留下评论