uvaoj 11029 Leading and Trailing 取log和快速幂 給定n和k,求n^k的最低三位和最高三位,數字很大,不能直接求出來。最低三位可以使用快速幂在logk的複雜度下解決。 對于最高三位,設log為以10為底的對數,那麼log(n^k)=klogn,這個值很容易算出來,我們設n^k用科學計數法表示為d*10^p,其中d為大于等于1小于10的實數,p為整數。那麼log(n^k)=klogn=log(d*10^p)=logd+p,因為d大于等于1小于10,是以logd為小數部分,10^logd*100的整數部分就是最高三位。 代碼如下:
/*************************************************************************
> File Name: 11029.cpp
> Author: gwq
> Mail: [email protected]
> Created Time: 2015年01月09日 星期五 18時38分18秒
************************************************************************/
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#define INF (INT_MAX / 10)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define pb push_back
#define sz(a) ((int)(a).size())
using namespace std;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef long long ll;
const double esp = 1e-5;
int main(int argc, char *argv[])
{
int t;
scanf("%d", &t);
while (t--) {
ll n, k;
scanf("%lld%lld", &n, &k);
ll m = n;
ll x = k;
ll ans = 1;
while (x != 0) {
if (x & 1) {
ans = (ans * m) % 1000;
}
m = (m * m) % 1000;
x >>= 1;
}
double t1 = k * log(n) / log(10);
double t2 = t1 - (ll)t1;
printf("%d", (int)(100.0 * pow(10, t2)));
printf("...%03lld\n", ans);
}
return 0;
}