Leading and Trailing（数论/n^k的前三位）题解-白红宇

Leading and Trailing（数论/n^k的前三位）题解

阅读量：6947 次

发布时间：2019-06-27

本文共 1625 字，大约阅读时间需要 5 分钟。

Leading and Trailing

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

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 < 2³¹) and k (1 ≤ k ≤ 10⁷).

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 n^k contains at least six digits.

Sample Input

123456 1

123456 2

2 31

2 32

29 8751919

Sample Output

Case 1: 123 456

Case 2: 152 936

Case 3: 214 648

Case 4: 429 296

Case 5: 665 669

思路：

n^k的后三位用快速幂。前三位计算方法：指数级一般用对数解决，令x为a^k整数部分, y为a^k小数部分，所以10^(x+y)==n^k，其中10^x是10.....0，那么10^y其实就是各个位数上的值，所以10^y前三位就是n^k前三位

新学了一个函数 double a=modf(double x,double *i )，返回x的整数部分给i，小数部分给a

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
              #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 0x3f3f3f3f#define ll long longconst int N=10000003; //18const int MOD=1000; using namespace std;int pow_mod(ll a,ll b){ ll ans=1; while(b){ if(b&1) ans=ans*a%MOD; a=a*a%MOD; b/=2; } return (int)ans;}int main(){ int T,res1,res2,num=1; ll a,k; double y; double x; scanf("%d",&T); while(T--){ scanf("%lld%lld",&a,&k); res2=pow_mod(a,k); y=modf((double)(k*log10(a)),&x); res1=floor(pow(10,y)*100); printf("Case %d: %d %03d\n",num++,res1,res2); } return 0;}

转载于:https://www.cnblogs.com/KirinSB/p/9409120.html

你可能感兴趣的文章

演示：外部全局地址与外部局部地址的使用案例