PID4 / 数列

PID4 / 数列

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

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

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

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

输入格式
输入只有1行，为2个正整数，用一个空格隔开：

k N

（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。

输出格式
输出为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10^9）。（整数前不要有空格和其他符号）。

输入样例：
3 100
样例输出：
981

思路：这个题刚开始自己看确实有些问题，主要是这个给的规律太明显却不好找，就是你明知道它有规律却不好总结，所以很麻烦，然后考虑了很久，也参考了别人大神们的代码，终于有了些思路。比如网上有大神说的这个题其实就是把输入的10进制数转换成2进制，然后通过二进制的规律对应底数，来输出数字，比如样例就是把100变成2进制数1100100，然后对应输出，3的6次方，加3的5次方，再加3的二次方。729+243+9=981。很有道理，具体的代码网上都有，我就不放了，接下来说我看到的第二种方法，其实也差不多，但是实现形式感觉简单很多，看代码：

#include <iostream>
using namespace std;
int main(){
    int k,N;
    cin>>k>>N;
    int sp=1,res=0;    //操作数，结果数
    do{
        if(N%2 == 1)  //如果N为奇数
	    {
            res=res+sp;    
        }
        sp=sp*k;     //每次循环sp乘上一次k
        if(N==1)
		{
			break;
		}
        N/=2;
    }
	while(true);
    cout<<res<<endl;
    return 0;
}

给的数字是100，
第一次100不是奇数，sp=3，N=50；
第二次50不是奇数，sp=9，N=25；
第三次25是奇数，res=9，sp=27，N=12；
第四次12不是奇数，sp=81，N=6；
第五次6不是奇数，sp=243，N=3；
第六次3是奇数，res=9+243，sp=729，N=1；
第七次1是奇数，res=9+243+729，然后N=1，break。

输出就是981。

算法原理就是判断N，其实和二进制数方法是一样的，每次除2其实就是判断一次二进制数的位。但是我自己觉得这个方法更加简便，就是没有二进制那么容易理解，但是其实是同一种方法。

结果：