快速幂可以节省大量计算时间
两种方式 递归和迭代 通常需要取模避免溢出
1.递归
#define Mod 100000int quick(int a,int n){ if(n==0) return 1; else if(n%2==1) { return quick(a,n-1)*a%Mod; } else { int temp = quick(a,n/2)%Mod; return temp*temp%Mod; }}
2,迭代
为了方便理解,从最初开始优化
例如 7^5 = (7^4)*(7^1)
4不断除2
= (49^2)*(7^1)
得到结果
比循环计算速度快,幂越大,速度差距越明显
#define Mod 100000int quick(int a,int n){ int result = 1;//结果 while(n>0)//幂次直到为0停止 { if(n%2==0)//次幂为偶数 { n = n/2; a=a*a%Mod; //相当于上文(7^4)中4变2,底数为49 } else//奇数先乘a,计算偶次幂的结果 { n = n-1; result = a*result%Mod; //对应上文 (7^5)中先乘7将5减一变偶数 n = n/2; a=a*a%Mod; } }
return result;}
语言方法
65521grA1r57K8
XFWtc
偏门行业75972009/04/12 01:44:02
合并简化代码
#define Mod 100000int quick(int a,int n){ int result = 1; while(n>0) { if(n%2==1) { result = a*result%Mod; } n = n/2; a=a*a%Mod; } return result;}
下列小小简化下
int quick(int a,int n){ int result = 1; while(n) { if(n&1) //n%2==1 判断为奇数 { result*=a; }
n>>1;//n = n/2 a*=a; }
return result;}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。