Power OJ 1163: 数列

青旅半醒 2021-09-28 05:06 319阅读 0赞

# [Power OJ 1163: 数列][Power OJ 1163_] #

## Description ##

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

## Input ##

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

## Output ##

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

#### 这道题其实是有一个小陷阱。 ####

#### 先分析题意： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyOTI2ODcw_size_16_color_FFFFFF_t_70]

#### 如图所示 ####

#### 规律如图所示，输入k，n； ####

#### 那么第n项为 ####

#### 先将n的化为2进制数列，然后以k为底，进行求和 ####

#### 例如样例中的3 100 ####

#### 100的二进制数列为1100100，那么第100项为3的6次方+3的5次方+3的2次方=981 ####

### 为什么说这道题有小陷阱呢，跟题目的要求有关。 ###

### 题目说结果均不超过2.1\*10^9 ###

### 我们来分析一下极限数据k=15 n=1000，很明显已经超过了题目的限定范围，这就是这道题为什么有小陷阱的原因，这道题因为题目限制所以只能用int型，数据超过范围，这和数据溢出又扯上了点关系，因此像pow函数也不能用，因为pow函数是返回的double，会导致数据大于题目要求，因此只能自己去写一个pow函数，让其返回的是int型 ###

### 样例代码如下 ###

#include<stdio.h>
    #include<stdlib.h>
    int p(int x,int y){ 
        int i,z=1;
        for(i=0;i<y;i++)
        { 
            z*=x;
        }
        return z;
    }
    int main()
    { 
        int a[99], i = 0;
        int n, k;
        scanf("%d%d", &k, &n);
        while (n != 0)
        { 
            a[i++] = n % 2;
            n /= 2;
        }
        int s = 0, j;
        for (j = 0; j < i; j++)
        { 
            s += a[j] * p(k, j);
        }
        printf("%d", s);
    }

[Power OJ 1163_]: https://www.oj.swust.edu.cn/problem/show/1163
[20190216214229893.png]: /images/20210923/ed533ab520a74e42bfc34205c3d7ee19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyOTI2ODcw_size_16_color_FFFFFF_t_70]: /images/20210923/56a5d4ff67fc4fa9a57fcd4c8f84daa7.png