首页 > 代码库 > 5200 fqy的难题----2的疯狂幂

5200 fqy的难题----2的疯狂幂

5200 fqy的难题----2的疯狂幂

 

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
 
 
题目描述 Description

大家都一定知道2的幂吧!

输入一个n,输出2的n次方

 

输入描述 Input Description

输入一个整数n,表示要求出2的n次方

输出描述 Output Description

只有一个整数,为2的n次方

样例输入 Sample Input

样例输入1:

6

 

样例输入2:

100

样例输出 Sample Output

样例输出1:

64

 

样例输出2:

1267650600228229401496703205376

 

数据范围及提示 Data Size & Hint

对于20%的数据,n<=50

对于50%的数据,n<=1500

对于100%的数据,n<=50000

分类标签 Tags 点此展开 

 
暂无标签
题解:
快速幂(递归版)+高精度乘法
~~非递归的暂时没搞出来
AC代码:
#include<cstdio>#include<iostream>#define ll long longusing namespace std;const int N=1e5+10;int num[N]={1,1};void MUL(int a[],int b[]){    int c[N]={0};    int l1=a[0];    for(int i=1;i<=l1;i++){        int x=0;        for(int j=1;j<=l1;j++){            c[i+j-1]+=a[i]*b[j]+x;            x=c[i+j-1]/10;            c[i+j-1]%=10;        }        c[i+l1]=x;    }    int j=l1<<1;    while(j>1&&!c[j]) j--;    for(int i=1;i<=j;i++) a[i]=c[i];    a[0]=j;}void mul(int a[]){    int &l=a[0];    for(int i=1;i<=l;i++) a[i]<<=1;    for(int i=1;i<=l;i++) a[i+1]+=a[i]/10,a[i]%=10;    if(a[l+1]) l++;}void fpow(int p){    if(!p) return ;    fpow(p>>1);    MUL(num,num);    if(p&1) mul(num);}int main(){    int n;cin>>n;    fpow(n);    for(int i=num[0];i;i--) printf("%d",num[i]);    return 0;}

 

 

5200 fqy的难题----2的疯狂幂