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 nk.

Input

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 < 231) and k (1 ≤ k ≤ 107).

Output

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 nk contains at least six digits.

Sample Input

5

123456 1

123456 2

2 31

2 32

29 8751919

Sample Output

Case 1: 123 456

Case 2: 152 936

Case 3: 214 648

Case 4: 429 296

Case 5: 665 669

---

题意:

求n ^ k的前3位数和后三位数.

思路:

后三位很好求,直接快速幂对1000取模即可.
问题关键在于后三位,我们知道 n ^ k 一定可以写成一个小数乘以10 ^ x的形式,那么我们列出等式 n ^ k = y * 10 ^ x,(这里我们定义y为一个只有一个小于10,大于等于1的小数),然后我们两边同时取对数可以得到:k * log(10) n = log(10) y + x;那么这样我们就可以算出y了,如何将y的值乘以100就为前3位

代码:

#include<cstdio>
#include<cmath>
using namespace std;

const int mod = 1e3;
int Pow(int x, int n){
    int ans = 1;
    int base = x % mod;
    while(n){
        if(n & 1) ans = ans * base % mod;
        base = base *base %mod;
        n = n >> 1;
    }
    return ans;
}

int main(){
    int t;
    scanf("%d", &t);
    int kase = 0;
    while( t--){
        int n, k;
        scanf("%d %d", &n, &k);
        int ans1 = Pow(n,k);
        double len = (double) (k * log10(n));
        int ans2 =(int)(pow(10.0, len - (int)len) * 100);
        printf("Case %d: %d %03d\n",++kase, ans2, ans1);
    }
    return 0;
}