1141 数列

2006年NOIP全国联赛普及组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

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

（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）

请你求出这个序列的第N项的值（用10进制数表示）。

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

输入描述 Input Description

只有1行，为2个正整数，用一个空格隔开：

k N（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）

输出描述 Output Description

为计算结果，是一个正整数(可能较大你懂的)。（整数前不要有空格和其他符号）

样例输入 Sample Input

3 100

样例输出 Sample Output

981

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开

数论 NOIP全国联赛普及组大陆地区 2006年

这题让我明白，要好好明白题目的用意，并好好观察题目，解题的方向就在里面。

这个数列就是一个二进制序列。我们只要把n转换成二进制数，再按k的幂展开求和就行啦。

风格1：

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
long long a[1001];
int main(){
    long long m,n,t,k=1;
    cin>>m>>n;
    for(int i=0;i<=1000;i++){
        t=k;
        for(int j=0;j<t;j++){
            a[k]=pow(m,i)+a[j];
            if(k==n){
                cout<<a[k]<<endl;
                return 0;
            }
            else k++;
        }
    }
    return 0;
}

风格2：

#include<cstdio>
#include<iostream>
using namespace std;
#define N 12
long long pw1[N],pw2[N],sum[N];
long long i,n,k,ans=0;
int main(){
    pw1[0]=1;pw2[0]=1;sum[0]=1;
    for(i=1;i<=10;i++)
        pw2[i]=pw2[i-1]*2,sum[i]=sum[i-1]+pw2[i];
    cin>>k>>n;
    for(i=1;i<=10;i++)
        pw1[i]=pw1[i-1]*k;
    while(n){
        for(i=0;i<=10;i++)
             if(pw2[i]>n) break;
        ans+=pw1[--i];
        n-=pw2[i];
    }
    cout<<ans<<endl;
    return 0;
}