数列
题目来源:NOIP2006普及组
时间限制:$1000ms$ 内存限制:$64mb$
题目描述
给定一个正整数 $k$ ,把所有 $k$ 的方幂及所有有限个互不相等的 $k$ 的方幂之和构成一个递增的序列,例如,当 $k=3$ 时,这个序列是:
$1,3,4,9,10,12,13,…$
该序列实际上就是:$3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…$
请你求出这个序列的第 $N$ 项的值( 用10进制数表示 )。
例如,对于 $k=3,N=100$ 时,正确答案应该是 $981$ 。
输入格式
输入1行,为 $k$、$N$ 两个正整数,用一个空格隔开。
输出格式
输出文件为计算结果,是一个正整数(在所有的测试数据中,结果均不超过$2.1∗10^9$)。
(整数前不要有空格和其他符号)。
数据范围
$3 ≤ k ≤ 15$ ,
$10 ≤ N ≤ 1000$
样例输入
3 100
样例输出
981
解题思路
继续延长题目给出的串为 $3^3,3^0+3^3,3^1+3^3,3^0+3^1+3^3,3^2+3^3,3^0+3^2+3^3,3^1+3^2+3^3,3^0+3^1+3^2+3^3,…$
即: $3,03,13,013,23,023,123,0123,…$
规律并不是按多项式的项数来排列的,所以无法用排列数算出具体的项数。
第一个思路:
3的次方上面观察规律,即对 $0,1,01,2,02,12,012,…$ 观察。
因为每一个次方的数在一项中仅出现一次,用二进制从右往左看,第几位有则第几位为1,其它位为0,比如第一项是 $0$,看成二进制从右往左第0位为1,即二进制的 $1$ ;第二项是 $1$ ,看成二进制从右往左第1位为1,即二进制的 $10$ 。
所以上面的串可以转换为 $1,10,11,100,101,110,111,…$
然后发现这段就是二进制的 $1,2,3,4,5,6,7,…$
所以第100项为:$1100100$,即 $2,5,6$ ,所以答案为 $3^2+3^5+3^6=981$
第二个思路:
观察数列 $1,3,4,9,10,12,13,…$ 发现:
其用三进制的表示为 $1,10,11,100,101,110,111,…$
然后发现这段就是二进制的 $1,2,3,4,5,6,7,…$
由此得到题解,将输入的 $N$ 用二进制的形式表示出来,然后再将其用 $k$ 进制展开转换为10进制。
解题代码-Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int k = input.nextInt();
String n = Integer.toBinaryString(input.nextInt());
input.close();
int j = n.length() - 1;
int ans = 0;
for (char ch : n.toCharArray()) {
if (ch == '1') {
ans += Math.pow(k, j);
}
j--;
}
System.out.println(ans);
}
}