首页 > 代码库 > [codevs1141]数列

[codevs1141]数列

[codevs1141]数列

试题描述

给定一个正整数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。

输入

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

k N(k、N的含义与上述的问题描述一致,且3≤k≤15,10≤N≤1000)

输出

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

输入示例

3 100

输出示例

981

数据规模及约定

见“输入

题解

二进制。注意开 long long。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
	return x * f;
}

#define LL long long

int k, n;
LL ans, num[15];

int main() {
	k = read(); n = read();
	
	num[0] = 1;
	for(int i = 1; i <= 11; i++) num[i] = num[i-1] * k;
	int t = 0;
	while(n) {
		ans += num[t] * (n & 1);
		t++; n >>= 1;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

 

[codevs1141]数列