(BC 一周年) hdu 5312 Sequence

Sequence

 

 Accepts: 25

 

 Submissions: 1442
 Time Limit: 2000/2000 MS (Java/Others)

 

 Memory Limit: 262144/262144 K (Java/Others)
问题描述

输出描述

输入样例

输出样例

比赛的时候没做出来.这道题需要用到的一个重要的性质是,任意一个自然数可以表示成至多三个三角形数(1,3,6,10,15…..)的和(orz高斯)然后也有推广到任意自然数可以表示成k个k角形数的和的结论(费马提出了猜想,柯西给了证明)然后官方题解说的比较好:

这个题看上去是一个贪心, 但是这个贪心显然是错的. 事实上这道题目很简单, 先判断1个是否可以, 然后判断2个是否可以. 之后找到最小的k (k > 2)k(k>2), 使得(m – k) mod 6 = 0(mk)mod6=0即可.

证明如下: 3n(n-1)+1 = 6(n*(n-1)/2)+13n(n1)+1=6(n(n1)/2)+1, 注意到n*(n-1)/2n(n1)/2是三角形数, 任意一个自然数最多只需要3个三角形数即可表示. 枚举需要kk个, 那么显然m=6(km=6(k个三角形数的和)+k)+k, 由于k ge 3k3, 只要m-kmk是6的倍数就一定是有解的.

事实上, 打个表应该也能发现规律.

另外还有一点,特判一个和两个的情况时,一个的好判断,扫一遍就好了

两个的话,由于这个数列是递增的,我们可以从两边往中间,算是一个不错的优化,具体见代码.

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz