2的N次方计算中结果可能超过long的范围
#include
#include
using namespace std;
void mult(int m[],int a);
void multipy(int n[],int m[]);
int mini(int a);
int main(void){
const int max = 200;
int m[max] = {0};
m[max-1] = 2;
int n[max] = {0};
int a;
cin >> a;
if(a%2==1)
n[max-1] = 2;
else
n[max-1] = 1;
while(a>1){
int s = mini(a);
for(int i = 0;i
m[i] = 0;
m[max-1] = 2;
mult(m,s);
multipy(n,m);
a -= s;
}
int z = 0;
while(n[z]==0)
z++;
for(int i = z;i
cout << n[i];
}
void mult(int *m,int a){
const int max = 200;
if(a==2){
int y = 0;
int e[max] = {0};
for(int i = max-1;i>=0;i--){
for(int j = max-1;j>=0;j--)
e[j-y] += m[i]*m[j];
y++;
}
for(int i = max-1;i>0;i--){
if(e[i]>9){
e[i-1] += e[i]/10;
e[i] %= 10;
}
}
for(int i = max-1;i>=0;i--)
m[i] = e[i];
}
else{
int y = 0;
int e[max] = {0};
for(int i = max-1;i>=0;i--){
for(int j = max-1;j>=0;j--)
e[j-y] += m[i]*m[j];
y++;
}
for(int i = max-1;i>0;i--){
if(e[i]>9){
e[i-1] += e[i]/10;
e[i] %= 10;
}
}
for(int i = max-1;i>=0;i--)
m[i] = e[i];
mult(m,a/2);
}
}
void multipy(int *n,int *m){
const int max = 200;
int y = 0;
int e[max] = {0};
for(int i = max-1;i>=0;i--){
for(int j = max-1;j>=0;j--)
e[j-y] += n[i]*m[j];
y++;
}
for(int i = max-1;i>0;i--){
if(e[i]>9){
e[i-1] += e[i]/10;
e[i] %= 10;
}
}
for(int i = max-1;i>=0;i--)
n[i] = e[i];
}
int mini(int a){
int k = 1;
while(k<=a)
k *= 2;
return k/2;
}