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<b<10，b取整數），則a=b*10^4就是N^N的前五位數，所以N^N=b*10^m=a*10^(m-4)，兩邊取對數得N*lg(N)=lg(b)+m=lg(a)+m-4;因為0<b<10（b取整數）,所以0<=lg(b)<1為小數部分。令x=lg(b)+m=lg(a)+m-4（m為x的整數部分m=floor(x)），x=N*lg(N)，則a=10^(x+4-m)=10^(x+4-(floor)x);這里用floor比較好，向下取整（而不是int，或者long?long，這樣可以避免溢出），即返回不大于x的最大整數。
pow(x,y)函數計算x的y次冪。②至于求后5位數就更簡單了，快速冪取余即可。
AC代碼：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 int mod_pow(LL base,LL n,int mod){
 5     LL res=1;
 6     while(n>0){
 7         if(n&1)res=res*base%mod;
 8         base=base*base%mod;
 9         n>>=1;
10     }
11     return res;
12 }
13 int main()
14 {
15     int n;
16     while(cin>>n && n){
17         printf("%0.0f %05d\n",pow(10,n*log10(n)-floor(n*log10(n))+4),mod_pow(n,n,100000));
18     }
19     return 0;
20 }

?

轉載于:https://www.cnblogs.com/acgoto/p/9017451.html

總結

以上是生活随笔為你收集整理的ACM_求N^N的前5位数和后5位数（数论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。