lightoj-1282 快速幂+数学

VJ题目链接:https://vjudge.net/problem/LightOJ-1282

题目大意

给你两个数$n,k$,$\left( 2\leq n\leq 2^{31}\right)$,$\left( 1\leq k\leq 10^{7}\right) $
让你求$n^{k}$的前三位数和后三位数

思路

$n^{k}$的后三位数很好求，直接快速幂然后对1000取模即可，
它的前三位数就要算一下
首先用科学计数法表示数，如$123465789=1.23456789\cdot 10^{8}$
那么$n^{k}=x\cdot 10^{len-1}$,其中$len$是$n^{k}$的位数，即$len=\lg \left( n^{k}\right) $
$$\therefore len=k\cdot \lg \left( n\right)$$
对这个式子$n^{k}=x\cdot 10^{len-1}$两边取对数得到
$$k\cdot \lg \left( n\right)=\lg \left(x\right)+\left( len+1\right)$$
这样就可以解出x，$n^{k}$的前三位就是x的前三位

AC代码

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
#define wfor(i,j,k) for(i=j;i<k;++i)
#define mfor(i,j,k) for(i=j;i>=k;--i)
// void read(int &x) {
//  char ch = getchar(); x = 0;
//  for (; ch < '0' || ch > '9'; ch = getchar());
//  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
// }
ll ksm(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    //std::ios::sync_with_stdio(false);
#ifdef test
    freopen("F:\\Desktop\\question\\in.txt", "r", stdin);
#endif
#ifdef ubuntu
    freopen("/home/time/debug/debug/in", "r", stdin);
    freopen("/home/time/debug/debug/out", "w", stdout);
#endif
    int t;
    scanf("%d", &t);
    int casecnt = 0;
    while (t--)
    {
        casecnt++;
        int n, k;
        scanf("%d %d", &n, &k);
        int anslast = ksm(n, k, 1000);
        int len = k * log10(n * 1.0);
        double x = pow(10, k * log10(n * 1.0) - len + 1);
        while (x < 100)
            x *= 10;
        int ans = floor(x);
        printf("Case %d: %03d %03d\n", casecnt, ans, anslast);
    }
    return 0;
}