[NOIP 2006 普及组] 数列

知识点

二进制映射、进制表示

解题思路

把N写成二进制，对每一位为1的第i位加入k^i，等价于把二进制数字串解释为k进制。

正确性说明

所有不同幂次子集与正整数的二进制表示一一对应。两子集的最高不同位为i时，k^i大于所有更低k次幂之和（k≥3），故数值大小与对应二进制整数顺序相同。第N项就由N的二进制映射得到。

易错点

不是求k的N次幂；结果可能超过32位，用64位保存；从低位累积时权重每次乘k。

复杂度

时间O(log N)，空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){long long k,n;cin>>k>>n;long long ans=0,p=1;while(n){if(n&1)ans+=p;p*=k;n>>=1;}cout<<ans<<'\n';}