快速幂取模就是在O(logn)内求出a^n mod b的值。算法的原理是ab mod c=(a mod c)(b mod c)mod c，因此很容易设计出一个基于二分的递归算法。
以下是我的代码，以下代码必须保证输入的是合法的表达式，比如不能出现0^0 mod b：
long exp_mod(long a,long n,long b)
{
long t;
if(n==0) return 1%b;
if(n==1) return a%b;
t=exp_mod(a,n/2,b);
t=t*t%b;
if((n&1)==1) t=t*a%b;
return t;
}
posted on 2010-04-04 19:18
lee1r 阅读(1327)
评论(2) 编辑 收藏 引用 所属分类:
算法与数据结构