数列 （C++代码）

/*
分析:
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加进去一个，然后要再加上前面所有的个数
如果到了某个n,加前面所有的大于N个,就扫下剩下的第几个就行
时间复杂度O(n)
f(n)=1+2*f(n-1)   fn表示有几个数目前
f(0)=1;
f(1)=3;
f(2)=7;
求得大于等于N时的n，然后N-f(n-1)剩下的从左边开始数
*/
#include<iostream>
#include<cstdio>
using namespace std;
int a[30000];
int main(void)
{
   int k , n ;
   while(scanf("%d%d",&k,&n)==2){
       int cnt = 0;
       int t = 1 ;
       for(int i=1;;i++){
            int  size = cnt;
            a[cnt++]=t;
            for(int j=0;j<size;j++)
            a[cnt++]= a[j]+t;
            t*=k;
            if(cnt>=n) break;
       }
       cout << a[n-1] << endl;
   }
    return 0;
}

解题思路:





注意事项:

不要使用pow()函数





参考代码: