lightoj 1282 && uva 11029

Leading and Trailing

lightoj 链接：http://lightoj.com/volume_showproblem.php?problem=1282

uva 链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1970

题意：给定 n， k ，求 n^k 的前3位和后三位的值。

思路：1、前 3 位：把 n^k 转化为 a.bc * 10^m，两边取 10 的对数得到 k * lg(n) = m + lg(a.bc) ( lg(a.bc) < 1 ) 。所以把 k * lg(n) 减掉整数部分(即 m )就可以得到

lg(a.bc) ，然后计算 10 ^lg(a.bc) * 100 就能得到答案。

　　2、后3位：把 k 化成二进制的数，进行快速幂取模运算，没难度。

代码：

lightoj 1282 代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 int n, k;
 8 
 9 int front(int n, int k)    //前3位
10 {
11     double s = k*log10(n) - (int) (k*log10(n));    //取对数
12     s = pow(10, s);
13     return s * 100;
14 }
15 
16 int rear(int n, int k) //后3位    
17 {
18     if(!k)    return 1;    //快速幂
19     LL s = rear(n, k/2);
20     if(k&1)    s = s*s % 1000 * n % 1000;
21     else    s = s*s % 1000;
22     return s % 1000;
23 }
24 
25 int main()
26 {
27     int t, i;
28     cin >> t;
29     for(i = 1; i <= t; ++i)
30     {
31         scanf("%d%d", &n, &k);
32         printf("Case %d: %d %03d
", i, front(n, k), rear(n, k));
33     }
34     return 0;
35 }

uva 11029 代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 int n, k;
 8 
 9 int front(int n, int k)    //前3位
10 {
11     double s = k*log10(n) - (int) (k*log10(n));    //取对数
12     s = pow(10, s);
13     return s * 100;
14 }
15 
16 int rear(int n, int k) //后3位
17 {
18     if(!k)    return 1;    //快速幂
19     LL s = rear(n, k/2);
20     if(k&1)    s = s*s % 1000 * n % 1000;
21     else    s = s*s % 1000;
22     return s % 1000;
23 }
24 
25 int main()
26 {
27     int t;
28     cin >> t;
29     while(t--)
30     {
31         scanf("%d%d", &n, &k);
32         printf("%d...%03d
", front(n, k), rear(n, k));
33     }
34     return 0;
35 }