UVA – 11029 输出前三位

题意:给定$a$和$n$,输出$a^n$的前三位和后三位

后三位快速幂

$log_{10}(a^n)=n\cdot log_{10}(a)=n\cdot log_{10}(x\cdot y),y<10,x mod 10 = 0$

$n\cdot log_{10}(x\cdot y)=p+q,q<1$,$p$作为整数只是倍数上的贡献,其中前三位就是$pow(10,q)\cdot 100$

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
using namespace std;
typedef long long ll;
ll fpw(ll a,ll n,ll mod){
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        n>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
int main(){
    int T; cin>>T;
    while(T--){
        ll a,n,mod;
        cin>>a>>n;
        ll ans2=fpw(a,n,1000);
        double tmp=(double)n*log10(a);
        tmp=tmp-(int)tmp;
        ll ans1=pow(10,tmp)*100;
        int len;
        if(ans2<10)len=1;
        else if(ans2<100) len=2;
        else len=3;
        cout<<ans1<<"..."<<string((3-len),'0')<<ans2<<endl;
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注