注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

UVa 374 Big Mod  

2009-04-20 22:17:10|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Big Mod

Calculate R=B^p mod M for large values of B, P, and M using an efficient algorithm. (That's right, this problem has a time dependency !!!.)

Input

Three integer values (in the order B, P, M) will be read one number per line. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.

Output

The result of the computation. A single integer.

Sample Input

3
18132
17

17
1765
3

2374859
3029382
36123

Sample Output

13
2
13195

题目就是求大数的余数,可以根据公式(a*b*c)%n=((a%n)*(b%n)*(c%n))%n来防止运算工程中的溢出。但是如果只是使用for循环来一个一个的求,由于时间限制,很容易TLE。这时候可以考虑用Divide & Conquer approach(分治法)。由于大部分的计算只要求出其中一半的余数,所以可以大大的降低时间复杂度。关键代码如下:

int bigMod(int b,int p,int m){
    int temp;
    if(p==0)return 1;
    if(p%2==0){            //每次只求出了一半的值,使得计算量减少
        temp=bigMod(b,p/2,m)%m;
        return (temp*temp)%m;
    }
    else return ((b%m)*bigMod(b,p-1,m))%m;
}

后记:在存在大量重复计算或可以将问题分解成等同的小问题的时候,可以考虑采用分治的方法来降低时间复杂度。

  评论这张
 
阅读(365)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017