整数次幂取模

浙江工业大学1052
整数次幂取模
Time Limit:1000MS  Memory Limit:32768K


Description:
给定一个数,其值用A的B次方表示(B<100000),求该数除以一个整数C(<100000)所得的余数。注意算法的合理性,其性能有一定的要求。每行有三个数,依次表示A,B,C,每行对输出对应的余数。

Sample Input:
1 2 3
2 1 3
3 3 5
Sample Output:
1
2
2

源代码:
#include<iostream>
using namespace std;

long power(long A,long B,long C)
{
    
if(B==0){
        
return 1;
    }

    
if(B==1){
        
return A%C;
    }


    
long tmp = power(A,B/2,C);
    
if(B&1==1){
        
return (((tmp*tmp)%C)*(A%C))%C;
    }
else{
        
return (tmp*tmp)%C;
    }

    
return 0;
}


int main()
{
    
long A,B,C;
    
while(scanf("%ld%ld%ld",&A,&B,&C)!=EOF){
        printf(
"%ld\n",power(A,B,C));
    }

    
return 0;
}



/*long long PowerMod(long long a, int b, int k)  
{   //(a^b )%k   
    long long tmp = a, ret = 1;  
    for(; b ; b>>1 )  
    {  
        if (b & 1)  
            ret = (ret * tmp) % k;  //只是每步运算的时候都取模   
        tmp = (tmp * tmp) % k;  
    }  
    return ret;  
}
*/



posted on 2011-11-10 16:59 DGQKing 阅读(358) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年11月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜