ACM_求N^N的前5位数和后5位数（数论）

NNNNN

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

对于整数N，求N^N的前5位和后5位（1057题加强版)

Input:

多组测试数据，每组测试数据输入为一个整数n（6 <= n <= 10^9），n为0时结束。

Output:

对每组测试输出为两个整数a和b，由空格隔开，保留前后0，格式见样例。

Sample Input:

6
10
110
1001
0

Sample Output:

46656 46656
10000 00000
35743 00000
27196 01001

解题思路：①怎么求N^N的前5位数呢？我们有对一个数N，用科学计数法表示为N=a*10^m，此时a的整数部分即为N的最高位数字。假设b是最高位数字（0
pow(x,y)函数计算x的y次幂。②至于求后5位数就更简单了，快速幂取余即可。

AC代码：

#include
using namespace std;
typedef long long LL;
int mod_pow(LL base,LL n,int mod){
    LL res=1;
    while(n>0){
        if(n&1)res=res*base%mod;
        base=base*base%mod;
        n>>=1;
    }
    return res;
}
int main()
{
    int n;
    while(cin>>n && n){
        printf("%0.0f %05d
",pow(10,n*log10(n)-floor(n*log10(n))+4),mod_pow(n,n,100000));
    }
    return 0;
}