428. 数列
给定一个正整数$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$行,为$2$个正整数,用一个空格隔开:$k N$。
输出格式
输出文件为计算结果,是一个正整数(在所有的测试数据中,结果均不超过$2.1∗10^9$)。(整数前不要有空格和其他符号)。
数据范围
$3≤k≤15,$
$10≤N≤1000$
输入样例:
3 100
输出样例:
981
思路:
表格显示不好看,贴个博客地址 day29 428 数列(二进制、映射)
我们发现将第n
项的n
转为二进制则有如下表格中的映射关系。
| 当前是第几项(n) |n对应的二进制 | 该项对应的序列 |
|–|–|–|
| 1 |1 | $3^0$ |
|2 | 10 | $3^1$ |
| 3| 11 |$3^0+3^1$ |
| 4 | 100 | $3^2$ |
| 5| 101 | $3^0+3^2$|
|6 | 110 | $3^1+3^2$ |
|7 | 111 | $3^0+3^1+3^2$ |
|… | … | … |
我们发现当n
表示为二进制数的情况下,当倒数第i
位是1
时,第n
项序列中便会出现$k^{i - 1}$。
如:$k = 3$ 时,第5
项的5
,二进制表示为101
,倒数第1
位是1
,故序列中会出现$3^0$,倒数第2
位是0
,所以没有出现$3^1$,而倒数第3
位是1
,故序列中出现了$3^2$,最终得到第5
项序列为$3^0+3^2$。
Java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int k = scanner.nextInt();
int n = scanner.nextInt();
int sum = 0;//题目告知了结果不超过21亿,故在int范围内
//n的数据范围在10~1000,而1024的二进制表示也才2^10,即十位二进制就可以表示完
//因此循环十次即可,每一次循环都是判断倒数第i位是否是1
for(int i = 0;i < 10;i++){
if((n >> i & 1) != 0){
sum += power(k,i);
}
}
System.out.println(sum);
}
//计算k的i方
private static int power(int k, int i) {
int res = 1;
while(i-- != 0){
res *= k;
}
return res;
}
}