AcWing寒假每日一题——Day27数列

数列

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

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

该序列实际上就是： 3 0 ， 3 1 ， 3 0 + 3 1 ， 3 2 ， 3 0 + 3 2 ， 3 1 + 3 2 ， 3 0 + 3 1 + 3 2 ， … 3^0，3^1，3^0+3^1，3^2，3^0+3^2，3^1+3^2，3^0+3^1+3^2，… 30，31，30+31，32，30+32，31+32，30+31+32，…
请你求出这个序列的第 N N N项的值（用 10 10 10进制数表示）。

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

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

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

数据范围
3 ≤ k ≤ 15 , 3≤k≤15, 3≤k≤15,
10 ≤ N ≤ 1000 10≤N≤1000 10≤N≤1000
输入样例：

3 100

输出样例：

981

分析： 转化为二进制加和即可

代码：

#include<bits/stdc++.h>
using namespace std;
int k,n;
int main(){
    int res=0;
    cin>>k>>n;
    for(int i=0;i<10;i++)
        if(n>>i&1) res+=pow(k,i);
    cout<<res<<endl;
}