LightOJ-1282 求幂的前三个和后三个有效数字

阅读量: searchstar 2019-04-10 23:52:32
Categories： Tags：

一种常见解法见链接：https://blog.csdn.net/gscsdlz/article/details/51886094
我数学不好想到了一个与众不同的解法。

求结果的前三位时，由于后面的数位对前三位的影响很小，所以不太重要，所以我们只要保证前若干位是精确的即可。这让我们想到可以用浮点数代替整数进行运算，后面不重要的数位会被自然舍弃，只保留前面的数位。
但是有一个问题，那就是浮点数能表示的数是有上限的，如果连续乘太多次会上溢。因此我们可以定义一个函数To1，将输入的double类型的x变成[1,10)上的数。

template<typename T>
void To1(T& x){
    while(x >= 1){
        x /= 10;
    }
    x *= 10;
}

每次运算完之后都把它重新放缩到[1,10)，就可以防止上溢啦。最后结果的前三个十进制数字即为所求。

int solve3(int x, int ex){
	double base = x;
    To1(base);
    double ans = 1;
	while(ex){
        if(ex & 1){
            To1(ans *= base);
        }
        if(ex >>= 1){
            To1(base *= base);
        }
    }
    while(ans < 1000)ans *= 10;
    return (int)(ans / 10);

但是，放缩会丢失大小信息，如果结果本身没有达到1000，那最后结果就会被过度放大，比如n = 2, k = 8时，结果是64，但是该函数会返回640。所以一开始先检查一下结果是否大于1000，如果不是则直接返回该结果。完整的函数如下：

int solve3(int x, int ex){
    LL tmp = 1;
    for(int i = 1; i <= ex; ++i){
        tmp *= x;
        if(tmp >= INT_MAX)break;
    }
    if(tmp < INT_MAX){
        Remain3(tmp);
        return (int)tmp;
    }

    double base = x;
    To1(base);
    double ans = 1;
    while(ex){
        if(ex & 1){
            To1(ans *= base);
        }
        if(ex >>= 1){
            To1(base *= base);
        }
    }
    while(ans < 1000)ans *= 10;
    return (int)(ans / 10);
}

其中的Remain3函数提取出输入参数的前三个有效数字：

template<typename T>
void Remain3(T& x){
    while(x >= 1000){
        x /= 10;
    }
}

求出结果的后三位有效数字用普通的快速幂对1000取模即可。完整AC代码如下：

#include <stdio.h>
#include <limits.h>

using namespace std;

typedef long long LL;

template<typename T>
T mpow(T base, int ex, T p)
{
    base %= p;
    T ans = 1;
    while(ex)
    {
        if(ex & 1)
            (ans *= base) %= p;
        if(ex >>= 1)
            (base *= base) %= p;
    }
    return ans;
}

template<typename T>
void To1(T& x){
    while(x >= 1){
        x /= 10;
    }
    x *= 10;
}

template<typename T>
void Remain3(T& x){
    while(x >= 1000){
        x /= 10;
    }
}

int solve3(int x, int ex){
    LL tmp = 1;
    for(int i = 1; i <= ex; ++i){
        tmp *= x;
        if(tmp >= INT_MAX)break;
    }
    if(tmp < INT_MAX){
        Remain3(tmp);
        return (int)tmp;
    }

    double base = x;
    To1(base);
    double ans = 1;
    while(ex){
        if(ex & 1){
            To1(ans *= base);
        }
        if(ex >>= 1){
            To1(base *= base);
        }
    }
    while(ans < 1000)ans *= 10;
    return (int)(ans / 10);
}

int main() {
    int n, k;

    int T;

    int ans_trailing;

    scanf("%d", &T);
    for(int Ti = 1; Ti <= T; ++Ti){
        scanf("%d%d", &n, &k);
        ans_trailing = 1;
        for(int i = 1; i <= k; ++i){
            ans_trailing *= n;
            if(ans_trailing >= 1000)break;
        }

        printf("Case %d: %d ", Ti, solve3(n, k));
        if(ans_trailing >= 1000){
            printf("%03d\n", mpow(n, k, 1000));
        }else{
            printf("%d\n", ans_trailing);
        }
    }
    return 0;
}

第一次写题解，如有不妥欢迎指出~

linux解压文件和创建压缩文件