POJ 1001 Exponentiation(高精度大数乘法)
程序员文章站
2024-03-17 22:57:22
...
题目链接:http://poj.org/problem?id=1001
题意:求小数R的N次幂
思路:结果数字串的长度最大为5*25,考虑用大数模板。先将小数转化为整数,输出时再考虑小数点位数。
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
#include <math.h>
#include <cstdio>
typedef long long LL;
using namespace std;
const int INF=INT_MAX;
const int MAXN=5005;
const int mod=1e9+7;
const int N = 1e4 + 10;
const double eps=1e-9;
int n;
char ans[6000000];
double m;
struct BigInt
{
const static int mod=10;
const static int mlen=1;
int a[600],len;
BigInt(int v=0)
{
memset(a,0,sizeof(a));
len=0;
do
{
a[len++]=v%mod;
v/=mod;
}
while(v);
}
BigInt(char s[])
{
memset(a,0,sizeof(a));
int slen=strlen(s);
len=(slen-1)/mlen+1;
int index=0;
for(int i=slen-1;i>=0;i-=mlen)
{
int t=0;
int j=max(0,i-mlen+1);
while(j<=i)
{
t=t*10+s[j]-'0';
j++;
}
a[index++]=t;
}
}
BigInt operator +(const BigInt &b)
{
BigInt ret;
ret.len=max(len,b.len);
memset(ret.a,0,sizeof(ret.a));
for(int i=0;i<ret.len;i++)
{
ret.a[i]+=(a[i]+b.a[i]);
ret.a[i+1]=ret.a[i]/mod;
ret.a[i]%=mod;
}
if(ret.a[ret.len]>0)ret.len++;
return ret;
}
BigInt operator *(const BigInt &b)
{
BigInt ret;
ret.len=len+b.len;
memset(ret.a,0,sizeof(ret.a));
for(int i=0;i<len;i++)
{
int up=0;
for(int j=0;j<b.len;j++)
{
int tmp=a[i]*b.a[j]+ret.a[i+j]+up;
ret.a[i+j]=tmp%mod;
up=tmp/mod;
}
if(up!=0)
{
ret.a[i+b.len]=up;
}
}
while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;
return ret;
}
void print()
{
printf("%d",a[len-1]);
for(int i=len-2;i>=0;i--)
printf("%d",a[i]);
}
void print2(int decn)
{
if(len<decn)
{
printf(".");
for(int i=0;i<decn-len;i++)
printf("0");
for(int i=len-1;i>=0;i--)
printf("%d",a[i]);
}
else if(decn==0)
{
for(int i=len-1;i>=0;i--)
printf("%d",a[i]);
}
else
{
for(int i=len-1;i>=decn;i--)
printf("%d",a[i]);
printf(".");
for(int i=decn-1;i>=0;i--)
printf("%d",a[i]);
}
}
};
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%lf%d",&m,&n)!=EOF)
{
int ten=1;
int cnt=0;
while(1)
{
double now=m*ten;
if(now-floor(now)<eps)
break;
ten*=10;
cnt++;
}
int t=(int)(m*ten+eps);
BigInt x(t);
BigInt ans(1);
for(int i=0;i<n;i++)
{
ans=ans*x;
}
ans.print2(cnt*n);
cout<<endl;
}
return 0;
}