P1517 高精求小数幂

程老师 · 2018-02-21 10:21:26 · 题解

【分析】

抛开小数不谈，本题求a^n，由于数字较大，要用到高精算法，n的值不大，可以不用快速幂。

本题a可能是小数，可以这样解决，先记录a的小数位数pt，并将a乘以10^pt，转化为整数a′，求出a′^n，设为s′，答案等于s′/(10×pt×n)，即输出时将s′的末尾pt×n位作为小数输出即可。

例：求1.25^2，先求125^2，等于15625，由于1.25有两位小数，1.25^2就有4位小数，所有结果等于1.5625。

【代码】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1300;      //100000^250有1250位 
int pt;
struct Bign{
    int s[MAXN], len;
    Bign(int num = 0){
        memset(s, 0, sizeof(s));
        len = 1;
        s[1] = num;
    }
    Bign operator * (int b)const{
        Bign c;
        c.len = len + 10;
        for (int i = 1; i <= c.len; i++){
            c.s[i] += s[i] * b;
            c.s[i+1] = c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }
    void clean(){
        while (len > 1 && !s[len]) len--;
    }
};
ostream& operator << (ostream &out, const Bign &x){
    int i;
    for (i = x.len; i > 0 && i > pt; i--)       //输出整数部分 
        out << x.s[i];
    if (i){                         //若i不为0，表示还有小数部分 
        out << ".";                 //先输出"." 
        for (i = pt; i > 0; i--)    //再输出小数部分 
            out << x.s[i];
    }
    return out; 
}
int main(){
    double a;
    int n; 
    while (cin >> a >> n){
        //求a的小数位数 
        pt = 0;                             //pt记录a的小数位数 
        while (fabs(a - round(a)) > 1e-6){  //若a不等于a的整数部分，表示a不是整数 
            pt++;                           //小数位数加一位 
            a *= 10;
        }
        pt *= n;                            //a^n的小数位数等于a的小数位数 ×n 
        //求s = a ^ n 
        Bign s = 1;
        for (int i = 1; i <= n; i++)
            s = s * (int)round(a);
        cout << s << endl;
    }
    return 0;
}