【蓝桥云课】快速幂

问题描述：快速求$a^b$

方法一：常规方法相乘$a\ast a\ast a\ast a\ast ...\ast a$
方法二：分治方法求$a^b$

$$a^b=\{\begin{array}{ll}1& \text{,b=0}\\ a& \text{,b=1}\\ a^{\frac{b}{2}}\cdot a^{\frac{b}{2}}& \text{,b为偶数}\\ a^{\frac{b-1}{2}}\cdot a^{\frac{b+1}{2}}& \text{,b为奇数}\end{array}$$

快速幂方法：扩底降幂方法

程序代码：

import java.util.Scanner;public class KuaiSuMi {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()) {int a=sc.nextInt();int b=sc.nextInt();int p=131;//计算a^bSystem.out.println(((int)Math.pow(a, b))%p);//系统自带计算方法System.out.println(funtion1(a,b));//常规方法System.out.println(funtion2(a,b));//分治方法System.out.println(funtion3(a,b,p));//(a^b)%pSystem.out.println(funtion4(a,b,p));//((a%p)(b%p))%pSystem.out.println(funtion5(a,b,p));//扩底降幂System.out.println(funtion6(a,b,p));//扩底降幂System.out.println(funtion7(a,b,p));//扩底降幂}}public static int funtion1(int a,int b) {int ans = 1;for(int i=1;i<=b;i++) ans = ans*a;return ans;}public static int funtion2(int a,int b) {if(b==0) return 1;if(b==1) return a;if(b%2==0) return funtion2(a, b/2)*funtion2(a, b/2);else return funtion2(a, (b-1)/2)*funtion2(a, (b+1)/2);}public static int funtion3(int a,int b,int p) {int ans = 1;for(int i=1;i<=b;i++) ans = ans*a;return ans%p;}public static int funtion4(int a,int b,int p) {int ans = 1;for(int i=1;i<=b;i++) ans = (ans*a)%p;return ans%p;}public static int funtion5(int a,int b,int p) {int ans = 1;while(b>0) {if(b%2==0) {a=a*a%p;//扩底b=b/2;//降幂} else {b=b-1;ans=ans*a%p;a=a*a%p;//扩底b=b/2;//降幂}}return ans;}public static int funtion6(int a,int b,int p) {int ans = 1;while(b>0) {if(b%2==1) ans=ans*a%p;a=a*a%p;//扩底b=b/2;//降幂}return ans;}public static int funtion7(int a,int b,int p) {int ans = 1;while(b>0) {if((b&1)!=0) ans=ans*a%p;a=a*a%p;//扩底b=b>>1;//降幂}return ans;}
}