k次方 求1个数的n次方的前三位数和后三位数

K次方

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 34   Accepted Submission(s) : 16

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

所有在程式设计已经有点经验的人都知道，当k很大时你无法完整的表达出n k。例如： C语言的函数 pow(123456,455)能够用double资料型态来表达，但是你却无法得到所有正确的数字。然而，若是能知道一些最左边（leading）和最右边（trailing）数字的话，也可稍微得到一些满足。

Input

输入的第一行有一个整数T（T < 1001），代表有几组测试资料。接下来的T行，每行有2个正整数n和k。n可以用32位元的整数表达，而k<10000001。

Output

每组测试资料输出一行，输出LLL...TTT的样式。其中LLL代表n k的最左边3个数字，TTT代表n k的最右边3个数字。例如123456 2 = 15241383936，所以你应该输出152...936。
你可以假设n k至少有6位数。

Sample Input

3
123456 1
123456 2
2100000056 67333

Sample Output

123...456
152...936
982...016

Author

shenlizhong
算法：

A、巧妙的思想，后三位用幂取模可以求出注意补0，总位数可利用t=k*log10((double)n)+1向上取整求出，前三位根据方程head=n^k/(10^(t-3))求出

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int pow_mod(int a,int n,int m)
{
    if(n==0)
    return 1%m;
    long long x=pow_mod(a,n/2,m);
    x=(x*x)%m;
    if(n%2)
    x=(x*a)%m;
    return (int)x;
}
int main()
{
    int T,n,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        int t=k*log10((double)n)+1,head,tail;
        tail=pow_mod(n%1000,k,1000);
        for(head=100;log(head)<=k*log(n)-(t-3)*log(10);head++);
        head--;
        printf("%3d...%03d\n",head,tail);//不足３位补０

    }
    return 0;
}