自动搬运

查看原文

来自洛谷，原作者为

	Starw 弱小和无知不是生存的障碍，傲慢才是|NOIP2024RP++

搬运于2025-08-24 21:02:50，当前版本为作者最后更新于2021-07-03 21:49:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里介绍一下做本题的三种方法（一种比一种快）。

1.常规做法：

时间复杂度 $O(n)$。

代码：

#include<bits/stdc++.h>//万能头
using namespace std;
int pow_2(int x){
	int ans=2;
   if(x==0) return 1;//这里需要特判一下2^0
	for(int i=2;i<=x;i++)
		ans*=2;
	return ans;
}
int main(){
	int n;
	scanf("%d",&n);
	printf("%d",pow_2(n));
	return 0;//好习惯*1
}

2.快速幂：

这里就不赘述了，详情请见P1226 【模板】快速幂||取余运算。

时间复杂度 $O(logn)$。

代码：

#include<bits/stdc++.h>//万能头
using namespace std;
int quick_pow(int n,int p){//快速幂
	int ans=1;
	while(p>0){
		if(p&1) ans=ans*n;
		p/=2,n*=n;
	}
	return ans;
}
int main(){
	int n;
	scanf("%d",&n);
	printf("%d",quick_pow(2,n));
	return 0;//好习惯*2
}

3.位运算：

这里要用到左移运算符 <<,这个东西的意思是把在它右边的数在二进制的情况下往左边移动它左边的数位，并自动用 $0$ 补齐，由于是二进制，所以 a<<b 就相当于 $a*2^b$。

时间复杂度 $O(1)$。

代码：

#include<bits/stdc++.h>//万能头 
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	printf("%d",1<<n);//位运算
	return 0;//好习惯*3
}