lightoj 1282 - Leading and Trailing

admin管理员组

文章数量:1530517

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of nk.

Input

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).

Output

For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that nk contains at least six digits.

题意:求n的k次方的前三位和后三位，后三位要补前导零。

求前三位的话：可以设 n^k = x*10^（len-1），len = (int) ( k*log(n) ) ,然后对原式两边同时取对数，就变成了 k*log（n） =  log（x * 10^(len-1) ）= log (x) + log(10 ^ (len-1) ) ，所以x = pow(10,1.0*k*log10(n)-len+1)，有同学就会说 了：“唉？len不就等于k*log(n)吗，跟这个k*log(n)不就消掉了吗”，注意这个pow里的k*log（n）是浮点型的，那个求得的len肯定是个整型，所以不能消掉。

求后三位的话：直接快速幂，对1000取模就好了。

#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long

using namespace std;


const int maxn = 1e6;
const int mod = 1000;

LL qucikpower(LL x,int k)
{
    LL ans = 1;
    while(k)
    {
        if(k & 1)
            ans = ans*x%mod;
        x = x*x%mod;
        k /= 2;
    }

    return ans;
}

int main(void)
{
    int T,n,k;
    scanf("%d",&T);
    int cas = 1;
    while(T--)
    {
        scanf("%d%d",&n,&k);
        int len = k*log10(n) + 1;
        double t = pow(10,1.0*k*log10(n)-len+1);
        while(t < 100)
            t*=10;
        int x = t;
        int y = qucikpower(n,k);
        printf("Case %d: %d %03d\n",cas++,x,y);
    }
    return 0;
}

本文标签： LightOJTrailingLeading