Leading and Trailing LightOJ - 1282

题意

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of <nobr> nk </nobr>.
求 <nobr> nk </nobr> 的最高三位和最低三位

分析

1 最低三位，快速幂取模
2 最高三位 任取一个数 n ，有 <nobr> t=lg(n),n=10t </nobr>其中 <nobr> t=x+y </nobr>，x为t的整数部分
,y 为t的小数部分 ,x 是n的位数，因为 n = <nobr> 10x </nobr> <nobr> n10x </nobr> ,其中 <nobr> y= lg </nobr> <nobr> n10x </nobr>, <nobr> 10y∗1000 </nobr>就是数n的前三位

参考代码

int qpow(int n,int k,int m)//快速幂
{
    int ans = 1;
    LL nn = n;
    nn %= m;
    while(k>0)
    {
        if(k&1)
            ans =ans * nn % m;
        nn = nn * nn % m;
        k>>=1;
    }
    return ans;
}
int main(void)
{
    std::ios::sync_with_stdio(false);
    int T;
    cin>>T;
    int kase = 0;
    // cout<<fmod(10.1,10);
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        double tmp = (double)k*log10(1.0*n);
        tmp = fmod(tmp,1);
        tmp = pow(10,tmp);
    while(tmp<100)
        tmp *= 10;
    int ans1 = (int) tmp;
        int ans2 = qpow(n,k,1000);
        //cout<<"Case "<<++kase<<": "<<ans1<<" "<<ans2<<endl;
        printf("Case %d: %d %03d\n",++kase,ans1,ans2);


    }
    return 0;
}