You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of n^k.

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers: n (2 ≤ n < 2³¹) and k (1 ≤ k ≤ 10⁷).

For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that n^k contains at least six digits.

5

123456 1

123456 2

2 31

2 32

29 8751919

Case 1: 123 456

Case 2: 152 936

Case 3: 214 648

Case 4: 429 296

Case 5: 665 669

题目大意：给两个数n、k，让求n^k的前三位和后三位

分析：

后三位直接用快数幂取余可以求出

前三位我们可以将n^k转化成a.bc * 10^m,这样abc就是前三位了，n^k =  a.bc * 10^m

即lg(n^k) = lg(a.bc * 10^m)

<==>k * lg(n) = lg(a.bc) + lg(10^m) = lg(a.bc) + m

m为k * lg(n)的整数部分，lg(a.bc)为k * lg(n)的小数部分

x = lg(a.bc) = k * lg(n) - m = k * lg(n) - (int)(k * lg(n))

a.bc = pow(10, x);

abc = a.bc * 100;

这样前三位数abc便可以求出

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

using namespace std;

typedef long long ll;

int Pow(int a, int b)

{

    int ans = ;

    a %= ;

    while(b)

    {

        if(b %  != )

            ans = (ans * a) % ;

        a = (a * a) % ;

        b /= ;

    }

    return ans;

}//快数幂

int main()

{

    int t, n, k, p = ;

    scanf("%d", &t);

    while(t--)

    {

        p++;

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

        double m = k * log10(n) - (int)(k * log10(n));

        m = pow(, m);

        int x = m * ;

        int y = Pow(n, k);

        printf("Case %d: %d %03d\n", p, x, y);

    }

    return ;

}