lightoj 1282 求n^k的前面3位和后面三位

末蓝、 2022-08-10 09:47 193阅读 0赞

1282 - Leading and Trailing

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge"><a href="http://lightoj.com/volume_submit.php?problem=1282" rel="nofollow"><img src="http://lightoj.com/images/submit1.png" alt=""> </a></td> 
   <td><a href="http://lightoj.com/volume_showproblem.php?problem=1282&amp;language=english&amp;type=pdf" rel="nofollow">PDF (English) </a></td> 
   <td><a href="http://lightoj.com/volume_problemstat.php?problem=1282" rel="nofollow">Statistics </a></td> 
   <td><a href="http://lightoj.com/forum_showproblem.php?problem=1282" rel="nofollow">Forum </a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td>Time Limit: <span style="color:#B45F04">2 second(s)</span></td> 
   <td>Memory Limit: <span style="color:#B45F04">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

You are given two integers: **n** and **k**, your taskis to find the most significant three digits, and least significant threedigits 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 leadingdigits (most significant) and three trailing digits (least significant). Youcan assume that the input is given such that **nk** contains atleast six digits.

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Sample Input</h1> </td> 
   <td> <h1>Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>5</p> <p>123456 1</p> <p>123456 2</p> <p>2 31</p> <p>2 32</p> <p>29 8751919</p> </td> 
   <td> <p>Case 1: 123 456</p> <p>Case 2: 152 936</p> <p>Case 3: 214 648</p> <p>Case 4: 429 296</p> <p>Case 5: 665 669</p> </td> 
  </tr> 
 </tbody> 
</table>

--------------------

Problem Setter: Shamim Hafiz

Special Thanks: Jane Alam Jan (Solution, Dataset)

题意：不说了。

分析：后面三位比较容易想到要用快速幂，模1000就行，注意要补足前导零。

前面三位可以把n的看次方表示成 x\*10^(len-1)  即有 n^k = x\*10^(len-1)，

两边取log，能把指数化掉，len是n^k的数位, len = log(n^k). 除了x，所有数都知道了，就可以算了。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=100100;
    
    ll power(ll a,ll n)
    {
        ll ret =1 ;
        while(n)
        {
            if(n&1) ret=ret*a%1000;
            a=a*a%1000;
            n>>=1;
        }
        return ret;
    }
    int main()
    {
        int T=in(),ii=1;
        while(T--)
        {
            int n =in(),k=in();
            int len=k*log10(n*1.0);
            double x=pow(10.0,k*1.0*log10(n*1.0)-len+1);
            while(x<100) x*=10;
            int pre=x;
            ll last = power(n,k);
            printf("Case %d: %d ",ii++,pre);
            if(last>=100) printf("%lld\n",last);
            else if (last>=10) printf("0%lld\n",last);
            else printf("00%lld\n",last);
        }
        return 0;
    }