题解 B2034 【计算 2 的幂】

· · 题解

题解

做法 1

在 \verb!cmath! 库中，有一个函数 \verb!pow! ，可以很方便地计算 x^y 。因此，本题只要输出 pow(2,n) 即可。

做法 2

有没有更好的做法呢？事实上， C++ 中你可以使用二进制左移运算符 \verb!<<! 来计算 a\cdot 2^b 的值。因此你只要输出 1<<n 即可。

快速幂

当然，我们不能仅限于此。如果我们计算的是 3^n ，或者跟一般地， m^n ，怎么做呢？显然，做法 1 当中的 pow(m,n) 照样可以用，但这样可能丢失精度，对于一些要取模的情况没有保证；做法 2 当中的 1<<n 仅限于 2 的若干次幂，对于 m 就无效了。

考虑将 n 二进制分解： \displaystyle n=x_0\cdot 2^0+x_1\cdot 2^1+\cdots x_k\cdot 2^k=\sum_{i=0}^k x_i\cdot 2^i ，其中 x_i\in\{0,1\} 。我们可以很轻易地计算出 m^2 ，将它平方后可以得到 m^4 ，同理可以推出 m^{2^k} 。因此：

m^n=\prod _{i=0}^k m^{2^i \cdot x_i}

将 n 二进制分解，我们就能很轻易地计算出 m^n 了。这种做法被称为快速幂。

参考代码

代码 1

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
int n;
int main(){
    cin>>n; cout<<(1<<n);
    return 0;
}

代码 2

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
int n;
int main(){
    cin>>n; cout<<(int)pow(2,n);
    return 0;
}