CodeRookie

用户名：Shmily124

访问量：120356

签　名：

清风前烹茶对弈，明月下把酒言欢

等　　级
排　　名	14
经　　验	21315
参赛次数	7
文章发表	39
年　　龄	0
在职情况	学生
学　　校	ZUA
专　　业	计科

　　自我简介：

悄悄地秃头，然后惊艳所有人？

TA的其他文章

2571: 蓝桥杯2020年第十一届省赛真题-回文日期（C++）
浏览：1348

2606: 蓝桥杯2021年第十二届省赛真题-左孩子右兄弟（C++）
浏览：1854

2612: 蓝桥杯2021年第十二届省赛真题-最少砝码
浏览：444

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1105: 数列数组模拟与位运算 C/C++

　　作者: CodeRookie　　　　发表时间：2022-05-09 23:33:31 浏览：336　|　评论：0　

原题链接：数列

### 模拟

看到 n 最大为 1000，那么暴力模拟也无所谓，复杂度也只不过 O(n)而已

定义一个数组

**每轮循环先在数组尾部加入新的指数幂**

**然后拿这个幂与此前的每一个数相加依次添加至数组尾部**

最终 arr[n - 1] 就是所求的答案

```cpp
#include <cstdio>

int k, n, sz = 0;	// sz表示当前数组里有效的数字个数 
int a[1005];

int main() {
	scanf("%d %d", &k, &n);
	for (int bac = 1; sz < n; bac *= k) {	// bac表示幂运算结果
		int m = sz;		//先记下当前有效个数 
		a[sz++] = bac;	//将新的幂运算加入尾部 
		for (int i = 0; i < m && sz < n; i++) {		//将新的幂与之前的结果相加 
			a[sz++] = a[i] + bac;
		}
	}
	printf("%d\n", a[n - 1]);
	return 0;
}
```

### 位运算

将 n 转化为 2 进制，可以发现

2 进制从右往左的第 i 位 ( i 从 0 开始) 对应着是否包含 k 的 i 次方

如下：

0001    对应    p^0

0010    对应    p^1

0011    对应    p^1 + p^0

0100    对应    p^2

……

**对 n 不断循环右移，每次循环判断最右一位是否为1**

**同时计算每一位对应幂运算的结果**

**若 (n & 1) == 1 则加上幂结果**

**直到 n 变为 0 停止**

时间复杂度 O(log(n))

```cpp
#include <cstdio>

int k, n; 
int main() {
	scanf("%d %d", &k, &n);
	int ans = 0, bac = 1;	//此处类型改为 long long 无法通过
	while (n) {
		if (n & 1) ans += bac;
		bac *= k;
		n >>= 1;
	}
	printf("%d\n", ans);	// 若用 long long 应改为 lld 占位符
	return 0;
}
```

题面上说：**（在所有的测试数据中，结果均不超过2.1*109）**

是在暗示结果不会超过 int 类型上限 ( int 类型最大为  2147483648 )

**然而这句话是骗人的……**

因为用 long long 来计算结果会无法通过最后一个样例

而 int 却可以，奇怪了，怎么会有 long long 过不了而 int 能过的答案

所以，**测试数据可能把 int 类型溢出后的结果当作了正确答案**

0.0分

4 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

CodeRookie

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

1642题解

Tom数（C语言代码）

1105: 数列数组模拟与位运算 C/C++

评论区

精彩推荐

陶陶摘苹果2 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

【计算直线的交点数】（C语言代码）

数列有序（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

1227题解

A+B for Input-Output Practice (II) （C++代码）

CodeRookie

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

1642题解

Tom数 （C语言代码）

1105: 数列 数组模拟与位运算 C/C++

评论区

精彩推荐

陶陶摘苹果2 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

【计算直线的交点数】 （C语言代码）

数列有序 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

1227题解

A+B for Input-Output Practice (II) （C++代码）

Tom数（C语言代码）

1105: 数列数组模拟与位运算 C/C++

　　评论区

【计算直线的交点数】（C语言代码）

数列有序（C语言代码）