[bzoj 1025][SCOI2009]游戏(DP)
题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1025
分析:首先这个问题等价于A1+A2+……Ak=n,求lcm(A1,A2,……,Ak)的种数
考虑一个Lcm=p1^a1 * p2^a2 * …… pk^ak 是否可能出现
WJMZBMR提出,能出现的充要条件是p1^a1+p2^a2+……+pk^ak<=n
证明:
先证必要性:
∵p1^a1 p2^a2 …… pk^ak 这k个数的最小公倍数正好是lcm 且 k<n (n以内的质数的个数肯定比n小啊)
∴可以把n分解成n=p1^a1 + p2^a2 …… +pk^ak + 1 + ……+1 (n-k个1),1对最小公倍数的大小lcm无影响
∴就存在这样的分解方案使得lcm能出现
再证充分性:
假设p1^a1+p2^a2+……+pk^ak>n
看个例子:27=12+8+6+1=2*2*3+2*2*2+2*3+1
他们的lcm=24=1^1 * 2^3 * 3^1
这个lcm如何求出来的呢?我们看看2的指数如何定:12分解质因数有2个2,8分解质因数有3个2,6分解质因数有1个2,所以lcm中2的指数就是max{2,3,1}=3, 以3为底数的指数也是如此求法。也就是说lcm里的每个质数对应的指数是对n分解的每一项中该质数个数的最大值!!!!
那么也就说对n的拆分里面,一定至少有一项含因子p1^a1,即对n的拆分里,一定至少有一项是p1^a1的倍数,同理也至少有一项分别是p2^a2 p3^a3 ……的 倍数,不妨设是b1*p1^a1 b2*p2^a2 ……
那么现在p1^a1+p2^a2+……+pk^ak>n
b1*p1^a1+b2*p2^a2+……+bk*pk^ak>n
注意bi*pi^ai是n的拆分中的一项,所以b1*p1^a1+b2*p2^a2+……+bk*pk^ak=n
很明显上面两个式子冲突了
于是假设不成立,一定有p1^a1+p2^a2+……+pk^ak<=n
综上所述,原问题等价于求满足p1^a1 + p2^a2 +…… pk^ak<=n的数列(a1,a2,...,ak)一共有多少个
这显然就是背包问题了……GG
这种神题只能欣赏了Orz……
最新文章
- opencv源码:cascadedetect
- Linux Swap分区设定
- Android IOS WebRTC 音视频开发总结(十六)-- 音频设备操作之opensl与jni
- [转]ldconfig几个需要注意的地方
- LCD驱动(FrameBuffer)实例开发讲解
- traits编程技法
- c#串口编程和单片机通信重大发现
- registerWithTouchDispatcher()函数的使用
- iOS开发之layoutSubviews
- 老李分享:接电话扩展之uiautomator 1
- 《奇思妙想》在JavaScript语言中floor和round方法在某种随机分配场景下对分配区间的公平性!!!
- oracle恢复已删除的表
- 【转】TCHAR
- vue开发中遇到的问题集锦(2)
- SpringBoot零XML配置的Spring Boot Application
- Android为TV端助力 关于Fragment你所需知道的一切!
- jquery ui autocomplete输入中文不自动完成的问题
- JS实现继承的6种方式
- 学习笔记之DevOps
- tar压缩/解压用法
热门文章
- python自动化测试学习笔记-8多线程
- Glide和Picassio的比较
- 406 Queue Reconstruction by Height 根据身高重建队列
- pyinstaller打包报错:AttributeError: &#39;str&#39; object has no attribute &#39;items&#39;
- .net环境下程序一些未知错误的调试
- ASP.NET中的<;%%>;介绍
- Android基础TOP6_2:Gallery +Image完成画廊
- ElasticSearch 安装使用
- C/C++ char*、char[]
- [转]汇编语言:MOVSB,MOVSW,MOVSD