UVA748 Exponentiation 题解
Comet387
·
·
题解
前言
其实很简单。但是要注意细节，还要高精度。
$\text{Updated on 2026/04/16}$：修改格式。
### 题意
多组数据，每组数据给定一个浮点数 $R$（$0<R<99.999$ 且 $R$ 在输入中只占用 $6$ 位字符）和一个整数 $n$（$0<n\leq25$），求 $R^n$（不能有前导 $0$ 或后导 $0$）。
### 思路
把 $R$ 的小数点去掉转换为整数（设为 $r$），然后计算 $r^n$，计算小数点的位置并在输出的时候处理即可。注意处理前导 $0$ 和后导 $0$。
### 代码（C++）
#### 部分代码（易于理解）
```cpp
#include<bits/stdc++.h>
using namespace std;
/*
省略 200 多行的高精度模板
提示：
1. Bignum x 代表定义高精度整数 x；
2. tval(s) 代表将字符串 s 转换为 Bignum 类型；
3. pow(x,y).s 代表计算 x 的 y 次方，返回 string。
*/
string s,ans;
int n,dot,getstr,st,ed,siz;
Bignum r;
int main()
{
while(cin>>s>>n) // 多测
{
dot=s.find('.');
s.erase(s.begin()+dot); // 去掉小数点
r=tval(s);
ans=pow(r,n).s; // 计算 r^n
siz=ans.size();
getstr=siz-((s.size()-dot)*n);
st=0,ed=siz-1;
while(ans[st]=='0'&&st!=getstr) ++st;
while(ans[ed]=='0'&&ed!=getstr) --ed;
// 前面 3 行确定前导 0 和后导 0 的结束位置
for(int i=st;i<=ed;++i)
{
if(i==getstr) cout<<'.'; // 判断输出小数点
cout<<ans[i];
}
cout<<endl; // 多测不换行，WA 两行泪
}
return 0;
}
```
#### 完整代码（带有高精度模板）
:::info[代码]
```cpp
#include <bits/stdc++.h>
using namespace std;
struct Bignum
{
string s;
int sz,f;
Bignum()
{
s="0",sz=1,f=1;
}
};
Bignum empty()
{
Bignum x;
x.s="",x.sz=0;
return x;
}
Bignum tval(string str)
{
Bignum x;
if(str[0]=='-')
x.f=-1,str=str.substr(1);
x.s=str,x.sz=str.size();
return x;
}
Bignum tval(int x)
{
Bignum ans;
if(x==0)
return ans;
ans=empty();
if(x<0)
ans.f=-1,x=-x;
while(x)
ans.s=char(x%10+'0')+ans.s,ans.sz++,x/=10;
return ans;
}
Bignum abs(Bignum x)
{
x.f=1;
return x;
}
Bignum opp(Bignum x)
{
x.f=-x.f;
return x;
}
istream &operator>>(istream &cin_,Bignum &x)
{
x=empty();
char ch=getchar();
while(ch<'0'||ch>'9')
x.f=(ch=='-' ? -1 : 1),ch=getchar();
while(ch>='0'&&ch<='9')
x.s+=ch,x.sz++,ch=getchar();
return cin_;
}
ostream &operator<<(ostream &cout_,Bignum x)
{
if(x.f==-1)
putchar('-');
for(int i=0;i<x.sz;i++)
putchar(x.s[i]);
return cout_;
}
bool operator<(Bignum x,Bignum y)
{
if(y.f==-1&&x.f==-1)
return y<x;
if(x.f==1&&y.f==-1)
return false;
if(x.f==-1&&y.f==1)
return true;
return x.sz<y.sz||(x.sz==y.sz&&x.s<y.s);
}
bool operator>(Bignum x,Bignum y)
{
return y<x;
}
bool operator>=(Bignum x,Bignum y)
{
return !(y<x);
}
bool operator<=(Bignum x,Bignum y)
{
return !(x>y);
}
bool operator==(Bignum x,Bignum y)
{
return (x>=y)&&(y<=x);
}
bool operator!=(Bignum x,Bignum y)
{
return !(x==y);
}
Bignum operator+(Bignum x,Bignum y)
{
if(x.f==-1&&y.f==-1)
{
x.f=y.f=1;
return opp(x+y);
}
if(x.f==-1&&y.f==1)
return y+x;
string a=x.s,b=y.s,res="";
int sa=x.sz,sb=y.sz;
if(x.f==1&&y.f==-1)
{
if(x<abs(y))
{
x.f=-1,y.f=1;
Bignum ans=y+x;
ans.f=-1;
return ans;
}
for(int i=sb;i<sa;i++)
b='0'+b;
int j=0;
for(int i=sa-1;i>=0;i--)
{
int t=a[i]-b[i]-j;
j=(t<0),t=(t+10)%10;
res=char(t+'0')+res;
}
while(res.size()>1&&res[0]=='0')
res=res.substr(1);
Bignum ans;
ans.s=res,ans.sz=res.size(),ans.f=1;
return ans;
}
if(sa>sb)
swap(a,b),swap(sa,sb);
Bignum ans;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
for(int i=sa;i<sb;i++)
a+='0';
int j=0;
for(int i=0;i<sb;i++)
{
int t=a[i]+b[i]-2*'0'+j;
j=t/10,t%=10,res+=char(t+'0');
}
if(j)
res+=char(j+'0');
reverse(res.begin(),res.end());
ans.s=res,ans.sz=res.size();
return ans;
}
void operator+=(Bignum &x,Bignum y)
{
x=x+y;
}
Bignum operator-(Bignum x,Bignum y)
{
y.f=-y.f;
return x+y;
}
void operator-=(Bignum &x,Bignum y)
{
x=x-y;
}
Bignum operator*(Bignum x,Bignum y)
{
if(x.f!=y.f)
{
x.f=y.f;
return opp(x*y);
}
string a=x.s,b=y.s;
int sa=x.sz,sb=y.sz;
if(a=="0"||b=="0")
return tval(0);
Bignum ans;
for(int i=sb-1;i>=0;i--)
{
string m;
int in=0;
for(int j=sa-1;j>=0;j--)
{
int t=(a[j]-'0')*(b[i]-'0')+in;
in=t/10,t%=10;
char c=t+'0',l=in+'0';
m=c+m;
if(j==0&&l>'0') m=l+m;
}
for(int j=1;j<=sb-1-i;j++)
m+='0';
ans+=tval(m);
}
return ans;
}
void operator*=(Bignum &x,Bignum y)
{
x=x*y;
}
Bignum pow(Bignum a,int b)
{
Bignum res=tval(1);
while(b)
res=res*(b&1?a:tval(1)),a*=a,b>>=1;
return res;
}
Bignum fac(int n)
{
Bignum res=tval(1);
for(int i=1;i<=n;i++)
res*=tval(i);
return res;
}
Bignum operator/(Bignum x,Bignum y)
{
if(x.f!=y.f)
{
x.f=y.f;
return opp(x/y);
}
x.f=y.f=1;
if(y>x)
return tval(0);
int cur=0;
Bignum tmp=empty(),ans=empty();
tmp.s=x.s[0],tmp.sz++;
while(cur<x.sz)
{
int res=9;
while(y*tval(res)>tmp)res--;
ans.s+=char(res+'0'),ans.sz++;
tmp-=y*tval(res);
if(tmp.s=="0")
tmp.s="",tmp.sz=0;
tmp.s+=x.s[++cur],tmp.sz++;
}
while(ans.sz>1&&ans.s[0]=='0')
ans.s=ans.s.substr(1),ans.sz--;
return ans;
}
void operator/=(Bignum &x,Bignum y)
{
x=x/y;
}
Bignum operator%(Bignum x,Bignum y)
{
return x-((x/y)*y);
}
void operator%=(Bignum &x,Bignum y)
{
x=x%y;
}
void operator++(Bignum &x)
{
x=x+tval(1);
}
void operator--(Bignum &x)
{
x=x-tval(1);
}
string s,ans;
int n,dot,getstr,st,ed,siz;
Bignum r;
int main()
{
while(cin>>s>>n)
{
dot=s.find('.');
s.erase(s.begin()+dot);
r=tval(s);
ans=pow(r,n).s;
siz=ans.size();
getstr=siz-((s.size()-dot)*n);
st=0,ed=siz-1;
while(ans[st]=='0'&&st!=getstr)
++st;
while(ans[ed]=='0'&&ed!=getstr)
--ed;
for(int i=st;i<=ed;++i)
{
if(i==getstr)
cout<<'.';
cout<<ans[i];
}
cout<<endl;
}
return 0;
}
```
:::
### 后记
其实试了用 Python（不用写高精度），但是会 TLE。