当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ1270数列(NOIP2006)
1574+

题目大意:一个序列中的元素为所有有限个互不相等的k的方幂之和,请问第n个是多少?

题目描述

给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是:

1,3,4,9,10,12,13,…

(该序列实际上就是:30,31,30+31,32,30+32,31+32,30+31+32,…)

请你求出这个序列的第N项的值(用10进制数表示)。

例如,对于k=3,N=100,正确答案应该是981。

输入

输入只有1行,为2个正整数,用一个空格隔开:

k  N (k、N的含义与上述的问题描述一致,且3≤k≤15,10≤N≤1000)。

输出

输出为计算结果,是一个正整数(在所有的测试数据中,结果均不超过2.1*109)。(整数前不要有空格和其他符号)。

样例输入

3 100

样例输出

981

提示

NOIP2006普及组第四题

解题思路

题目保证答案在int范围内,k最小是3,最极端的情况下,幂小于20,因为2^30超过int范围,不会用到。

也就是说,对于所有的k,其幂小于20。数据很小,我们可以暴力枚举每种幂选不选,最后选了的求和得到数字。全部存起来,排序输出第n个值就行。

注意:全不选是不行的,所以0这个值要排除;去重有很多种方法,其实不会有重复,如果不想证明那就写个去重。

程序实现

写完爆搜,很容易想到其实跟二进制有关。对于第x位,0表示不选,1表示选,选了的话加k^x;如果k=2,跟二进制的带权展开一样的,2^0+2^1+…+2^x = 2^(x+1) – 1 < 2 ^ (x+1),对于更大的禁止,更加不会有重复。第n个,如果n的二进制是10001000,那么他就是k^7+k^3。

About

坚决不Copy代码!

本文标签:,,,,,,,,

SSOJ1270数列(NOIP2006):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!