題意
給出兩個數n和k
求出 的前三位和后三位

思路：
先考慮 的后三位我，們在求后三位的時候，只需要快速冪計算 并且對100取模即可
$$\begin{gathered} 再來考慮前三位 \\ 任何一個數都能寫成n^k=10^x?10^y \\ 其中x為整數部分、y為小數部分 \\ 那我們考慮x和y分別是什么含義 \\ 10的x整數次冪就是1后面0的個數，相當于存著的長度部分， \\ 10^y=\frac{n^k}{10^x}就相當于存著的數值部分 \\ 換句話說n^k總共x+1位，10^x?10^y是n^k的前x+1項， \\ 那么我們求n^k的前3項只需要求10^2?10^y即可 \end{gathered}$$

算法：那么我們要如何求呢
$$\begin{gathered} n^k很大不可能直接對其求，那么我們由 \\ \lg n=x+y所以 \\ {n}^k=10^{(x+y{)}^k=10^{kx+ky}} \\ 所以對上邊的(x+y)?k就得到了 \\ （這里可能有的人轉不過來來，要明確我們找的就是k（x+y), \\ 前邊求出了x+y,那么乘k就可以了 \\ 不過我們想要的是y \\ 那么只需要k(x+y)?[k(x+y]就好[]是下取整。 \end{gathered}$$

AC 代碼：

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define max 2000 #define mod 1000ll pow_mod(ll a, ll i) //快速冪 {if (i == 0) //遞歸終止條件return 1 % mod;ll temp = pow_mod(a, i >> 1);temp = temp * temp % mod;if (i & 1) //是奇數temp = (ll)temp * a % mod;return temp; }int main() {ll t;while (cin >> t){for (ll i = 1; i <= t; ++i){ll n,k;cin >> n>>k;ll after = pow_mod(n, k); //后三位ll count = 0, temp = n;double ret = log10(n*1.0); //求對數 *1.0 確保精度ret *= (double)k;ret = ret - (int)ret; //取整數部分//cout << ret << endl;cout << "Case " << i << ": " << (int)((pow(10, ret)) * 100) << " ";printf("%03lld\n", after);}}return 0; }

快速冪可以參考該文章：
快速冪

總結

以上是生活随笔為你收集整理的Leading and Trailing（数论题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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