LightOJ - 1282 Leading and Trailing（求幂结果的前k位和后k位）

传送门

---

题目大意

求$n^k(n<2^{31},k\le 1e7)$的前$3$位和后$3$位

解题思路

对于后三位来说，只需要快速幂然后对$1000$取模，但是这个前三位怎么求我怎么也想不出来，后来看了题解才恍然大悟：

$n^k$用科学计数法表示为$n^k=a\ast 10^b$，其中$a$是小数，将两边取对数，这样可以得到$klo{g}_{10}n=b+lo{g}_{10}a$，仔细观察这个式子，因为$b$一定是整数，而$0<a<10$，那么$lo{g}_{10}a$一定是小于0的小数，所以左边结果的小数部分就是$lo{g}_{10}a$的结果，然后再求$10$的对应次幂即可

意后三位可能有前导零

// // Created by Happig on 2020/10/20 // #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define Vector Point #define ENDL "\n" #define lowbit(x) (x&(-x)) #define mkp(x, y) make_pair(x,y) #define mem(a, x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double dinf = 1e300; const ll INF = 1e18; const int Mod = 1e9 + 7; const int maxn = 2e5 + 10; ll qkp(ll x, ll n, ll p) { ll ans = 1; x %= p; while (n) { if (n & 1) ans = ans * x % p; x = x * x % p; n >>= 1; } return ans; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T, kase = 0, n, k; scanf("%d", &T); while (T--) { cin >> n >> k; //double temp = fmod((double) k * log10(n), 1.0); double temp = (double) k * log10(n) - (int) ((double) k * log10(n)); int ans1 = pow(10.0, temp) * 100; int ans2 = qkp(n, k, 1000); printf("Case %d: %d %03d\n", ++kase, ans1, ans2); //cout << "Case " << ++kase << ": " << ans1 << " " << ans2 << endl; } return 0; }