2869.md

移位运算 2869: 计算费马数

计算费马数需要进行2的指数幂运算，2在二进制计算机系统中有着特殊的地位，因此可以采用特有的移位运算来简化操作。

题目来源

2869: 计算费马数

总时间限制: 1000ms 内存限制: 65536kB

描述

费马数是一个正整数序列{Fn}，它的表达式为Fn = 2^2^n + 1，n = 0, 1, 2, ...

编写程序，输出前 k 个费马数 F0, F1, F2, ...

要求：

　　1、不能使用指数函数power

　　2、不能使用查表法，必须在程序里计算费马数

输入

非负整数k

输出

前k个费马数

样例输入

3

样例输出

3
5
17

题目的描述实际上要求计算的Fn为2^(2^n) + 1，因此可以采用两级左移运算，左移一位即乘以2，考虑到IO流操作和符号优先级需要增加括号。题目没有给出k的取值范围，这里我用了long long类型进行尝试，可以通过，对于较大的k需要考虑高精度运算，以后的题目会碰到。

#include <iostream>
using namespace std;
int main() {
	int k, i;
	cin >> k;
	for (i = 0; i < k; ++i)	{
		cout << (1ll << (1 << i)) + 1 << endl;
	}
	return 0;
}

2869.cpp 代码长度：160B 内存：128kB 时间：1ms 通过率：97% 最小内存：128kB 最短时间：0ms

这个题目要求输出前k个费马数，所以1层循环是必需的。另外针对此类题可以考虑存储中间过程值，毕竟随着k的增大，可以在先前计算结果的基础上继续，但内存需求可能有所增加。本题由于可以使用移位运算，存储耗费的时间也差不多。

有任何的改进意见欢迎大家在微信平台公众号主页面留言或者发表issue。