题解 1105: 数列

解题思路:

（1）观察序列：3⁰，3¹，3⁰+3¹，3²，3⁰+3²，3¹+3²，3⁰+3¹+3²，…

（2）发现可以写成：3⁰*1，3¹*1+3⁰*0，3¹*1+3⁰*1，3²*1+3¹*0+3⁰*0，3²*1+3¹*0+3⁰*1，3²*1+3¹*1+3⁰*0，3²*1+3¹*1+3⁰*1，…

（3）对于数列中的每一个数，都可以表示为一系列3^m*(1 or 0)的形式。

（4）多项式中的1和0提取出来，就是1，10，11，100，101，110，111，…即原数列中数的位置的二进制表示，第1个数对应1，第2个数对应10，第3个数对应11，……

（5）至于指数 m ，它的大小是和二进制的位数有关的，最低位对应 m = 0，之后随着位数递增。

（6）理解了数列的表示方式，就可以写出底数为 k 的数列的第 N 项了，就是把 N 写成二进制，每位乘以对应的 k 的方幂，再求和就得到了结果。

注意事项:

（1）int k, N, res, order; 这句编译时会把除了 order 以外的变量初始化为0，而 order 初始化为51，必须在定义时就初始化 order = 0 才行，我无法理解。
（2）求方幂用 pow() 函数的话会报答案错误，只能写成用 for 循环累乘的形式，我没开会员所以不知道为啥错了。

参考代码:

// 题目 1105: 数列
#include <iostream>
#include <cmath>

using namespace std;

int main() {
	int k, N;
	cin >> k >> N;
	int res = 0;   // 最后结果
	int order = 0; // 数位，代表幂，从 0 开始
	while (N) {
		if(N % 2 == 1) {
			// res += pow(k, order); //用 pow() 会报答案错误？？？
			int temp = 1;
			for (int i = 0; i < order; ++i) {
				temp *= k;
			}
			res += temp; // 如果二进制N的最低位是1，则加上对应的数字
		}
		N /= 2;  // 舍去最低位
		++order; // 位数+1
	}
	cout << res << endl;
	return 0;
}