UVa 11029 Leading and Trailing

UVa 11029 Leading and Trailing (如何计算n^k的开头三位和末尾三位？)

11029 - Leading and Trailing

Time limit: 3.000 seconds

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

Apart from the novice programmers, all others know that you can’t exactly represent numbers raised to some high power. For example, the C functionpow(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 andk 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…TTT, where LLL represents the first three digits ofn^k and TTT represents the last three digits of n^k. You are assured thatn^k will contain at least 6 digits.

思路：后三位好求，mod=1000的快速幂就是。

那前三位怎么求呢？——对数

令x=lg(n^k)的整数部分，y=lg(n^k)的小数部分，则n^k由y决定——因为10^x是1000...0。所以10^y再乘上100取整就是前三位。

完整代码：

/*0.015s*/

#include<cstdio>
#include<cmath>
#define sf scanf
#define pf printf
typedef long long ll;
const int mod = 1000;  

ll pow_mod(int n, int k)
{
    if (k == 0) return 1;
    ll temp = pow_mod(n, k >> 1);
    temp = temp * temp % mod;
    if (k & 1) temp = temp * n % mod;///注意这里中间运算结果会超int
    return temp;
}  

int main()
{
    int t, n, k;
    double intpart;
    sf("%d", &t);
    while (t--)
    {
        sf("%d%d", &n, &k);
        pf("%d...%03lld\n", (int)pow(10.0, 2.0 + modf((double)k * log10(n), &intpart)), pow_mod(n, k));
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， uva
， double
， temp
， and
， lead
The
leading and trailing、uva11029、leading trailing、ios leading trailing、leading and lagging，以便于您获取更多的相关知识。