LightOJ - 1282 Leading and Trailing 题解

题目大意

解题思路

这个题目需要解决两个问题

输出\(n^{k}\)的前三位
输出\(n^{k}\)的后三位

输出后三位

这个比较好解决，使用快速幂和模运算就能解决，这里不再详细介绍，看代码就行了。

输出前三位

这个比较麻烦，因为\(n^{k}\)会相当大，即使long long类型也不能存下来，那个我们就要想办法来降低这个结果的位数。

怎么办呢？使用对数来降低位数

\[lg{n^{k}}=k*lg{n}
\]

\[n^{k}=10^{lg{n^{k}}}=10^{k*lgn}
\]

这样\(k*lgn\)的整数部分提供位数，小数部分提供精度，我们需要去掉整数只保留小数部分。

需要注意的是就算\(10^{0.0001}>1\)（根据指数函数）,即10的小数部分次幂也是大于零的，这样我们把这个结果载乘以100就是前三位了（因为小数点前面已经有1了）。

代码实现

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

using namespace std;

int n,k;

int qpow(int n,int k) //快速幂模板

{

    int ans=1,base=n%1000;

    while(k)

    {

        if(k%2==1)

        {

            ans=(ans*base)%1000;

        }

        base=(base*base)%1000;

        k/=2;

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    for(int i=1; i<=t; i++)

    {

        scanf("%d%d",&n,&k);

        double a=(double)k*log10(n*1.0); //注意这个log函数的参数需要是浮点数，double类型

        a-=(int)a; //去掉整数部分

        double pre=pow(10.0,a); //求10的小数部分次幂

        printf("Case %d: %d %03d\n",i ,(int)(pre*100),qpow(n, k)); //处理输出即可

    }

}

lg