ACM数论 求幂乘

反复平方法

____________________________________________________________________________________________________________________________

pow(x,n)

当n==0时

函数等于1；

当n==偶数时

函数等于pow(x^2,n/2)；

当n==奇数时

函数等于pow(x^2,n/2)*x；

举例子

3^21

3^21=(3*3)^10*3

9^10=(9^9)^5

81^5=(81*81)^2*81

6561^2=(6521*6521)

___________________________________________________________________________________________________________________________

pos(x,n)

if n==0

return 1

res=pow(x^x,n/2)

if(n是奇数)

res=res*x

return res

ACM数论 求幂乘

原文：http://www.cnblogs.com/PapperTown/p/7261890.html