题解 | #数列#

题目描述

给定一个正整数k( 3 ≤ k ≤ 15 ),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k = 3时，这个序列是： 1，3，4，9，10，12，13，…（该序列实际上就是：） 请你求出这个序列的第N项的值（用10进制数表示）。例如，对于k = 3，N = 100，正确答案应该是 981。

输入描述：

输入1行，为2个正整数，用一个空格隔开：k N（k、N的含义与上述的问题描述一致，且3 ≤ k ≤ 15，10 ≤ N ≤ 1000 ）。

输出描述：

输出一个正整数（在所有的测试数据中，结果均不超过）。（整数前不要有空格和其他符号）。

示例1

输入

3 100

输出

981

思路

聚焦于，可以看到当k的方幂的幂次最大为m-1时，序列长度为 ，其中m为正整数。由于 。 所以当k的方幂的幂次最大为m的序列的前项与k的方幂的幂次最大为m的序列相同，第项为,而在这之后的前项与序列的前项几乎相同，区别只是多加了个。（从第0项开始算）

这样就足以写下以下代码。

#include<cstdio>
#include<cmath>
int main()
{
    int i=0,k,n;
    scanf("%d%d",&k,&n);
    long*b=new long[n];
    while(1)
    {
        int p=pow(2,i);
        b[p-1]=pow(k,i++);
        for(int l=p;l<2*p-1;++l)
        {
            b[l]=b[p-1]+b[l-p];
            if(l==n-1)
            {
                printf("%ld\n",b[l]);
                delete[]b;
                return 0;
            }
        }
    }    
}

完事后看了下别人的代码，发现是既简洁又高效。研究了下思路：

k 的方幂及所有有限个互不相等的 k 的方幂之和构成一个递增的序列。
序列形式：

简直是在描述二进制数：

2 的方幂及所有有限个互不相等的 2 的方幂之和构成一个递增的二进制序列。

二进制：

位表示：

10进制数：

因此可以这么看，
， （从第1项开始算）。由此可以根据n的二进制位表示构造出这个序列第n项的值。 实现如下：

#include<cstdio>
#include<cmath>
int main()
{
    int i=0,k,n;
    scanf("%d%d",&k,&n);
    long b=0;
    do b+=n%2*pow(k,i++);while(n/=2);
    printf("%ld",b);
}