注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

SCOI 2010 幸运数字 ( bzoj 1853) 容斥原理、lcm  

2014-03-15 10:11:56|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这道题第一眼看起来像是数位DP(毕竟才学了数位DP 很多都容易往上面去想)
不过呢 既然pv中提示是容斥原理,显然是不方便用数位DP的
之前做过两道容斥原理的题都是标准的 O(n*2^n)容斥部分的复杂度
这道题根据某些题解中说的 先枚举出只含6和8的都有2000个了 显然不是一般的那种
不过如果数学好点的话(像我就太渣了),是可以利用一个性质的——
X以内a或b的倍数
=X/a+X/b-X/lcm(a,b)
=X/lcm(1,a)+X/lcm(1,b)-X/lcm(a,b);
推广可知
X以内a或b或c的倍数
=X/a+X/b+X/c-X/lcm(a,b)-X/lcm(b,c)-X/lcm(a,c)+X/lcm(a,b,c)
=X/lcm(1,a)+X/lcm(1,b)+X/lcm(1,c)-X/lcm(a,b)-X/lcm(b,c)-X/lcm(a,c)+X/lcm(a,b,c)
多个数的就很明显了
考虑到lcm多做几次就会超过10^10了
所以从大到小排一遍再+return的话 实际效果是很好的
最后附赠一道一样的题(双倍经验)——bzoj 2393
  评论这张
 
阅读(142)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017