UVA - 11029 - Leading and Trailing （快速幂+公式变形） - c++编程基础

TOP

UVA - 11029 - Leading and Trailing （快速幂+公式变形）

2015-11-21 01:03:48 来源: 作者: 【大中小】浏览:1次

Tags：UVA 11029 Leading and Trailing 快速公式变形

思路：后三位可以直接快速幂取模，然后前三位可以有两种做法，一个是利用double，一个是利用公式法，具体看代码吧

注意，后三位不足三位要补0，即用%03d

AC代码①：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #define LL long long #define INF 1000000000 using namespace std; #define MOD 1000 int T; int n, k; int kmod(int x, int n) { //快速幂 int ret = 1; while(n) { if(n & 1) ret = (ret * x) % MOD; x = (x * x) % MOD; n >>= 1; } return ret; } double kkmod(double x, int n) { //利用double来求前三位 double ret = 1; while(n) { if(n & 1) ret = ret * x; while(ret >= INF) ret /= INF; x = x * x; while(x >= INF) x /= INF; n >>= 1; } return ret; } int main() { scanf(%d, &T); while(T --) { scanf(%d %d, &n, &k); int ttt = n % 1000; ttt = kmod(ttt, k); double lll = kkmod((double)n, k); lll *= 1000; //可能lll本来就小于1000，可能还不足三位 while(lll >= 1000) { lll /= 10; } /*char str[1234]; sprintf(str, %lf, 1000 * lll); str[3] = '';*/ //也可以这样输出前三位 //printf(%lf , lll); printf(%d...%03d , (int)lll, ttt); //记住后三位用%03d，要严格按照格式输出 } return 0; }

AC代码②：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              #include 
             
               #define LL long long #define INF 0x7fffffff using namespace std; int T; int n, k; int kmod(int x, int n) { int ret = 1; while(n) { if(n & 1) ret = (ret * x) % 1000; x = x * x % 1000; n >>= 1; } return ret; } int main() { scanf(%d, &T); while(T --) { scanf(%d %d, &n, &k); int lll, ttt; lll = kmod(n % 1000, k); ttt = (int)pow(10, 2 + fmod(k * log10(n), 1)); //利用公式变形来求前三位 printf(%d...%03d , ttt, lll); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 1257最少拦截系统（贪心）	下一篇：Codeforces Round #207 (Div. 1) ..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: