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
#include
#include
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;
}