算法1
(位运算,二进制) $O(\log N)$
题目中所给的序列为互不相等的k的方幂之和构成一个递增的序列,因此序列中第n个数可以表示为:
$a[n] = b_{m-1}k^{m-1} + b_{m-2}k^{m-2} + … + b_{1}k^{1}+ b_{0}k^{0}$, 其中$b_i = 0\ 或\ 1$
也就是$a[n]$可以表示为若干互不相等的k的幂的组合。
接下来我们考察$a[n + 1]$的组合情况,注意$a[n + 1]$是比$a[n]$大的最小的数。
如果$a[n]$中,$b_0 = 0$,那么$a[n + 1]$ = $a[n] + k^0$。
否则,我们应该找到从右往左数,第一个是0的$b_i$,将其置为1,且将$b_i$右边的$b_j (j < i)$全部置为0
在由$a[n]$推导出$a[n + 1]$的过程中,我们发现,从二进制角度看待$a[n]$ 的系数$(b_{m-1}b_{m-2}…b_2b_1b_0)_2$,这个二进制数+ 1即为$a[n + 1]$的系数。
$a[1] = k^0(1), a[2] = k^1(10), a[3] = k^1 + k^0 (11)....$
所以$a[n]$的系数就是n的二进制表达。
于是:
设N的二进制表示为$(b_{m-1}b_{m-2}…b_2b_1b_0)_2$
其中$b_i = 0\ 或\ 1$
那么答案为$\sum\limits_{i=0}^{m-1} b_i \cdot k^i $
时间复杂度
每次循环将n右移一位,故时间复杂度为$O(\log N)$
C++ 代码
#include <iostream>
using namespace std;
int k, n;
int main(){
cin >> k >> n;
int res = 0;
int w = 1;
while (n){
if (n & 1) res += w;
w *= k;
n = n >> 1;
}
cout << res;
return 0;
}