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;
    }
}