快速幂 E - Leading and Trailing LightOJ

快速幂 E - Leading and Trailing LightOJ - 1282

阅读量：5080 次

发布时间：2019-06-12

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

快速幂主要是把n拆成2进制位，如果这一位有那么就乘，没有就不乘，而计数器也就是x是不断推进的，从x->x^2->x^4直到n的最高位

精髓在于取模，后一步的要求结果只与前一步的模后数据有关。

对于后三个数用了log10.log函数对求n^k这种问题还是很有用的。没想出来。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
         5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 using namespace std;13 const double Pi=3.14159265358979323846;14 typedef long long ll;15 const int MAXN=5000+5;16 const int dx[5]={ 0,0,0,1,-1};17 const int dy[5]={ 1,-1,0,0,0};18 const int INF = 0x3f3f3f3f;19 const int NINF = 0xc0c0c0c0;20 ll mod_pow(ll n,ll x,ll mod)21 { 22 ll ans=1;23 while(n>0){24 if(n&1) ans=ans*x%mod;25 x=x*x%mod;26 n>>=1;27 }28 return ans;29 }30 31 int main()32 {33 int cnt=0;34 int t;cin>>t;35 while(t--)36 {37 ll n,k;cin>>n>>k;38 ll last=mod_pow(k,n,1000); 39 double p=k*log10(n);40 ll x=(ll)p;double y=p-x;41 y=pow(10,y)*100;42 ll first=int(y);43 printf("Case %d: %03lld %03lld\n",++cnt,first,last);44 }45 return 0; 46 }