[原创]UVA 11029 Leading and Trailing [数学]

2016-06-28 21:47:05 Tabris_ 阅读数：244

博客爬取于2020-06-14 22:44:20
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51779048

Apart from the novice programmers, all others know that you can’t exactly represent numbers raised
to some high power. For example, the C function pow(125456, 455) can be represented in double data
type format, but you won’t get all the digits of the result. However we can get at least some satisfaction
if we could know few of the leading and trailing digits. This is the requirement of this problem.
Input
The first line of input will be an integer T < 1001, where T represents the number of test cases. Each
of the next T lines contains two positive integers, n and k. n will fit in 32 bit integer and k will be less
than 10000001.
Output
For each line of input there will be one line of output. It will be of the format LLL . . . T T T, where
LLL represents the first three digits of n
k and T T T represents the last three digits of n
k
. You are
assured that n
k will contain at least 6 digits.
Sample Input
2
123456 1
123456 2
Sample Output
123…456
152…936

题目大意 就是求 n^k 的前三位和后三位

题解 :
后三位很好处理了 直接快速幂取模就好了

前三位就比较复杂了

n^k=A 同时取log
klog(n)=log(A) => A=10^(klog(n))

在这里我们知道k*log(10) =a.b (a是整数部分，b是小数部分)

在这里 a对A 的贡献就是一堆0 所以并没有什么用

所以A=10^(b)
因为要取 A 的前三位 所以A= 10^(2+b) 即可

还有一个坑点 就是后三位数如果是 12 的话 要输出012 就是前导0要有 wrong 了无数发

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <limits.h>
# include <malloc.h>
# include <ctype.h>
# include <math.h>
# include <string>
# include <iostream>
# include <algorithm>
# include <map>
# include <vector>
# include <set>

using namespace std;

# define LL unsigned long long int

LL qmod (LL a,LL b,LL mod)
{
    LL res=1;
    while(b)
    {
        if(b&1) res=(res*a)%mod;
        b >>= 1;
        a=(a*a)%mod;
    }
    return res;
}

LL  solve(int n, LL m,int weishu)
{
    weishu-=1;

    LL p, q, ans;
    double f = m*log10(n);

    //接下来三行就是求f的小数部分的
    q = (LL)f;
    p = (LL)(f*10000000)-q*10000000;
    double x = 1.0*p/10000000;

    ans = (LL)(pow(10, x+weishu));
    return ans;
}

int main()
{
    int t,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        LL a= qmod(n,k,1000) ;
        LL b= solve(n,k,3) ;
        printf("%lld...%03lld\n",b,a);
    }
    return 0;
}