Light oj 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 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=10^(k*log10(n));

令b=k*logn10(n),求出b的小数部分b=b-(int)b;然后求pow(10,b)*100，就是前三位；

例如：123456=1.23456*10^5=10^log10(1.23456)*10^5=10^(5+log10(1.23456));

b=5+log10(1.23456),小数部分为log10(1.23456),则pow(10,log10(1.23456))=1.23456,1.23*100=123.456,转化为整形就求得了前三位；

代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
long long quick_pow(int n,int k)
{long long base=n,ans=1;while(k){if(k&1){ans=(ans*base)%1000;}base=(base*base)%1000;k>>=1;}return ans;
}
int main()
{int n,k,t,mm=1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);double b=k*1.0*log10(n*1.0);b=b-(long long)b;//求小数部分； long long ans1=pow(10,b)*100;//求出来的是小数，强制转换为long long整形;long long  ans2=quick_pow(n,k);//求后三位； printf("Case %d: %lld %03lld\n",mm++,ans1,ans2);}return 0;
}