人见人爱A^B

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 22425 Accepted Submission(s): 15667

Problem Description 求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”

Input 输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。
Output 对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

Sample Input

Sample Output

8
984
1第一发 数论，问题描述：求 a^n%m最简单的思想是用循环分部取余，在n很小的情况下是可以过的，如下#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               using namespace std; int main() { int a,b; while(cin>>a>>b) { if(!a&&!b)break; int p=1; for(int i=1;i<=b;i++) p=p*a%1000; cout<
              
               
但是当n很大的时候这个循环就要挂掉了，所以要用到数学方法。对指数n进行二分，就会有a^n%m= a^(n/2)%m n为偶数 a^(n/2)%m * a%m n为奇数非递归 代码如下：
               #include 
                
                 
#include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         #include 
                        
                          #include 
                          #include 
                          
                            using namespace std; #define LL long long LL multimod(LL a,LL n,LL m) { LL ans=1,tem=a; while(n) { if(n&1)//判断是否为奇数 ans=ans*tem%m; tem=tem*tem%m; n/=2; } return ans; } int main() { LL a,b; while(cin>>a>>b) { if(!a&&!b)break; cout<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：NeHe OpenGL lession 2	下一篇：uva 261 - The Window Property(..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: