1019 - [NOIP2006]数列

题意：

给定正整数, k所有互不相等的方幂构成一个严格递增的序列,求此序列的第N项.

思路一 找规律

1. 第项的值为
   
2. 每个第项会连续出现次, 每项均为 k的方幂组成的集合的子集 + 注:n个元素集合的所有子集数量为

思路二 类比二进制

根据思路一中的规律，可以类比到二进制数据的存储。
--若k=2(并不在测试用例范围中),则原数列完全就是一个正整数集,因此可以直接使用二进制转十进制的代码,只需替换掉2
(相当于数位仅可为0/1的k进制数)

具体代码（C++）：

思路一：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=0;

void solve(int k, int n){
    if(n==0){
        return;
    }
    if(n==1){
        ans+=1;
        return;
    }
    int times=1;
    while(pow(2,times)<=n){
        times++;
    }
    n-=pow(2, times-1);
  
    ans+=pow(k, times-1);
    solve(k, n);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, n;
    cin>>k>>n;
    solve(k, n);
    cout<<ans;
    return 0;
}

思路二：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=0;

void solve(int k, int n){
    int power=0;
    while(n){
        if(n%2){
            ans+=pow(k, power);
        }
        power++;
        n>>=1;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, n;
    cin>>k>>n;
    solve(k, n);
    cout<<ans;
    return 0;
}

题外话

明明在题目中说好了"在所有的测试数据中，结果均不超过",但变量ans在数据类型为int时还是不能AC