Leading and Trailing LightOJ - 1282（快速幂）

我就是我 2023-07-04 14:17 38阅读 0赞

# Leading and Trailing LightOJ - 1282（快速幂）  #

[题目链接][Link 1]

**题意：**  
即：非常明显的快速幂，求最终结果的前三位和最后三位

**题解：**  
由于这里是大数相关的问题，最初想到的肯定是Java的BigInteger，但是tle了…  
悲剧了  
一番挣扎后，还是没有想出来，看了题解发现果然还是太菜，关于幂运算求前三位有个固定的式子：

int ans1=(int)pow(10.0,2+fmod(k*log10(n),1));

然后对于后三位，只需要在快速幂时，进行取模运算就可以了，于是结果就已经呼之欲出了

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    #define mod 1000
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn=1000010;
    const double eps=1e-8;
    int t;
    int n,k;
    int modPow(int a,int b){
        
        int r=1;
        a%=1000;
        while(b){
        
            if(b&1){
        
                r=r*a%mod;
            }
            b>>=1;
            a=a*a%mod;
        }
        return r;
    }
    int main(){
        
        scanf("%d",&t);
        int cnt=1;
        while(t--){
        
            scanf("%d%d",&n,&k);
            int ans1=(int)pow(10.0,2+fmod(k*log10(n),1));
            while(ans1>1000){
        
                ans1/=10;
            }
            int ans2=modPow(n,k);
            ans2%=1000;         //最终结果可能大于1000，需要再次取模，踩过坑
            printf("Case %d: %d %03d\n",cnt++,ans1,ans2);
        }
        return 0;
    }

[Link 1]: https://vjudge.net/problem/LightOJ-1282