简单快速幂

快速幂可以节省大量计算时间

两种方式  递归和迭代 通常需要取模避免溢出

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;}