题解 | 数列-NOIP2006普及组复赛C题

C-数列_NOIP2006普及组复赛

https://ac.nowcoder.com/acm/contest/234/C

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

3 100

输出

981

解答

其实前面的”用10进制表示“暴露了一切，嘿嘿，我们可以以题目的k=3为例，转换成3进制：

1	3	4	9	10	12	13
1	10	11	100	101	110	111

啊哈，好像二进制诶！把这个看成二进制再变成十进制看看

1	3	4	9	10	12	13
1	2	3	4	5	6	7

不就是n吗？好神奇啊，再换成k=4试试

1	4	5	16
1	10	11	100
1	2	3	4

那么我们就反过来推就行啦！大功告成！

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long a[1001],n,k,l=0;
int main()
{
    long long ans=0;
    scanf("%lld%lld",&n,&k);
    while(k!=0)a[++l]=k%2,k/=2;
    for(long long i=l;i>=1;i--)ans+=pow(n,i-1)*a[i];
    printf("%lld\n",ans);
    return 0;
}

来源：candy_c

全部评论

推荐最新楼层

emitter26

河北经贸大学 C++

#include<iostream> #include<cmath> using namespace std; //像题解中写的一样，该题扎眼看上去的规律性不那么强，但是对于本题的“用十进制数表示” //会显得十分可疑，联想到别的数迎难而解 int main() { int k,n; cin>>k>>n; int sum=0,ans=0; int a[1001]={0}; int l=0; while(n)//模拟对于十进制数转二进制数的方法进行求解，用数组去进行存储 { a[l++]=n%2; n/=2; } for(int i=l-1;i>=0;i--)//求出每个位置上k的次幂，然后对于数组的01去进行关于该数的 //取舍，这很合理 { ans+=pow(k,i)*a[i]; } cout<</cmath></iostream>

1 回复分享

发布于 2023-09-16 14:21 河北