P1517 高精求小数幂【洛谷算法习题】

P1517 高精求小数幂网页链接P1517 高精求小数幂题目描述计算量非常大、精度要求非常高的问题是很常见的。举个例子计算国家债务就是这么一项对于许多计算机系统来说非常繁重的工作。现在有这么一个任务要求编写一个程序来计算R n R^nRn的精确值其中R RR是一个实数( 0 R ≤ 9999.9 ) (0 R \le 9999.9)(0R≤9999.9)而n nn是一个整数( 1 ≤ n ≤ 250 ) (1 \le n \le 250)(1≤n≤250)。输入格式本题有多组数据。对于每组数据一行两个数字R , n R,nR,n中间有至少一个空格。保证每行包括空格在内恰好有9 99个字符且n nn后面没有空格。请读入到输入文件末尾对于 C 的std::cin可以使用while (std::cin s n) {/* ... */}来实现这一功能其中s是std::string类型的变量。对于 C/C 的scanf可以使用while (scanf(%s%d, s, n) 2) {/* ... */}来实现这一功能其中s是char*类型的变量。对于其他输入函数实现这一功能的方式请自行查阅文档。保证数据组数不超过11 1111组。输出格式对于每组数据输出一行一个实数表示R n R^nRn的精确值。输出有三点要求输出不允许有前导0 00。小数部分末尾不能有0 00。如果结果是整数不应该输出小数点。特别地当答案小于1 \bm 11时你需要省略整数部分的0 \bm 00输出形如.25的答案。输入输出样例 #1输入 #195.123 2 0.4321 5 5.1234 7 6.7592 3 98.999 5 1.0100 10输出 #19048.385129 .01506334182914325601 92663.3181348508776705891407804544 308.806114738688 9509420210.697891990494999 1.10462212541120451001解题思路本题是高精度小数幂运算的经典题型核心思路是将小数乘法转化为整数高精度乘法通过记录小数位数统一还原小数点位置最后按格式要求处理前导零、末尾零与小数点。1. 问题等价转化任意小数R RR均可表示为R X / 10 d R X / 10^dRX/10d其中d dd是R RR的小数位数X XX是R RR去掉小数点后的整数。因此R n R^nRn等价于X n / 10 d × n X^n / 10^{d \times n}Xn/10d×n。通过该转化可将小数幂运算完全转化为整数的高精度乘法问题最后再插入小数点即可规避了直接处理小数的复杂度。2. 高精度整数乘法采用低位在前的数组存储方式下标1对应个位下标越大位数越高通过竖式乘法实现两个大整数相乘遍历第一个数的每一位与第二个数逐位相乘累加到结果数组的对应位置。逐位处理进位保证每一位数值在 0~9 范围内。3. 小数点还原与格式处理累乘完成后总小数位数为初始小数位数乘以指数n nn。按以下步骤处理输出格式小数末尾去零移除小数部分最右侧的所有无效零。整数前导去零移除整数部分最左侧的所有无效零。特殊规则适配若小数部分全为零省略小数点仅输出整数部分。若整数部分全为零结果小于1省略整数部分的0直接以小数点开头如.25。代码中采用整体反转的巧妙设计先按低位在前拼接小数、小数点、整数部分统一去除两端无效零后再整体反转一次性得到符合顺序和格式要求的结果。4. 幂运算实现由于指数n nn最大为250直接采用朴素累乘即可初始结果为底数循环n − 1 n-1n−1次每次乘以原始底数。数据组数不超过11组总运算量完全在时间限制内。总结核心逻辑将小数转化为整数做高精度乘法通过记录小数位数还原小数点借助反转技巧统一处理格式与零的裁剪最终得到精确结果。关键操作小数转整数的等价转化、低位在前的竖式乘法、整体反转式格式处理、两端零裁剪。效率保障指数规模小朴素累乘无性能压力高精度运算位数仅千级运行开销极低。代码简要说明rev 辅助函数反转字符串的指定区间用于将低位在前的计算结果转换为正常的高位在前输出顺序。mul 乘法函数分别统计两个参数字符串的小数位数求和得到总小数位数dot。去掉小数点将数字部分逆序存入数组 A、B低位在前个位对应下标1。执行竖式乘法逐位相乘并处理进位得到结果数组 C。按「小数部分 小数点 整数部分」的顺序拼接字符串均为低位在前的顺序。从后往前裁剪整数前导零从前往后裁剪小数末尾零。若剩余有效部分以小数点开头跳过小数点起始位置。反转有效区间得到正常顺序且符合格式要求的结果字符串。主函数逻辑循环读入每组数据的底数字符串与指数n nn。保存原始底数base将初始结果s累乘n − 1 n-1n−1次 base得到最终幂结果。直接输出处理好的结果字符串。注意细节当n 1 n1n1时代码直接输出原始输入字符串未做格式裁剪若输入包含末尾零可能不符合输出要求。实际测试中指数通常≥2不影响通过。结果数组长度预留充足高位补零不影响最终结果裁剪步骤会自动去除无效零。输入优化关闭流同步并解绑 tie提升多组数据的读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;stringrev(string a,ll l,ll r){string b;for(ll ir;il;i--)ba[i];returnb;}stringmul(string a1,string b1){string res;ll dot0;ll laa1.size(),lbb1.size();vectorllA(la1,0),B(lb1,0);ll fa0,fb0;for(ll i0;ila;i){if(a1[i].){dotla-i-1;fa1;break;}}for(ll i0;ilb;i){if(b1[i].){dotlb-i-1;fb1;break;}}ll tala-fa,tblb-fb;vectorllC(lalbdot5,0);for(ll i0;ila;i){if(a1[i]!.){A[ta]a1[i]-48;ta--;}}for(ll i0;ilb;i){if(b1[i]!.){B[tb]b1[i]-48;tb--;}}for(ll i1;ila;i){ll carry0;for(ll j1;jlb;j){C[ij-1]A[i]*B[j]carryC[ij-1];carryC[ij-1]/10;C[ij-1]%10;}C[ilb]carry;}ll idx1,totallalbdot;while(dot--){reschar(C[idx]48);idx;}res.;while(idxtotal){reschar(C[idx]48);idx;}idx--;while(res[idx]0)idx--;ll st0;while(res[st]0)st;if(res[st].)st;resrev(res,st,idx);returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s;ll n;while(cinsn){string bases;for(ll i0;in-1;i)smul(s,base);coutsendl;}return0;}