LightOJ - 1282 Leading and Trailin（快速幂，对数求大数前3位）

链接：LightOJ - 1282 Leading and Trailin

题意：

给出$n(2\le n<2^{31})$ 和 $k(1\le k\le 10^7)$，问$n^k$的前三位和后三位分别为多少？
（题目保证$n^k$最少有6位）

分析：

$n^k$的后三位直接快速幂对1000求模即可，比较难处理的是前三位。

设 前三位为$x$，$n^k$共有$m$位，则有：（ [x]代表对x向下取整 ）
$$x=\left[\frac{n^k}{10^{m?3}}\right]$$
将其化为：
$$x=\left[10^{\lg \frac{n^k}{10^{m?3}}}\right]$$
$$\lg \frac{n^k}{10^{m?3}}=\lg n^k?\lg 10^{m?3}=k\lg n?m+3$$
$$?x=\left[10^{k\lg n?m+3}\right]$$
其中 $m=[\lg n^k]+1=[k\lg n]+1$

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL qpow(LL a,LL b,LL c)
{
    LL res=1;while(b){
    if(b&1)res=(res*a)%c;a=(a*a)%c;b>>=1;}return res;
}
int main()
{
    int T,kase=1;scanf("%d",&T);while(T--){
    LL n,k;scanf("%lld %lld",&n,&k);double m=floor(k*log10(n))+1;   //floor()即向下取整（也可使用强制类型转化）printf("Case %d: %.f %03lld\n",kase++,floor(pow(10,k*log10(n)-m+3)),qpow(n,k,1000));//后三位要注意输出前导零}return 0;
}