大屯街道网站建设,盗版小说网站怎么做的,wordpress 去谷歌,网站建设做的好问题描述#xff1a;快速求aba^bab
方法一#xff1a;常规方法相乘a∗a∗a∗a∗...∗aa*a*a*a*...*aa∗a∗a∗a∗...∗a 方法二#xff1a;分治方法求aba^bab ab{1,b0a,b1ab2⋅ab2,b为偶数ab−12⋅ab12,b为奇数a^b\begin{cases} 1 \text{,b0}\\ a \text{,b1}\\ a…问题描述快速求aba^bab
方法一常规方法相乘a∗a∗a∗a∗...∗aa*a*a*a*...*aa∗a∗a∗a∗...∗a 方法二分治方法求aba^bab
ab{1,b0a,b1ab2⋅ab2,b为偶数ab−12⋅ab12,b为奇数a^b\begin{cases} 1 \text{,b0}\\ a \text{,b1}\\ a^{\frac{b}{2}} · a^{\frac{b}{2} } \text{,b为偶数}\\ a^{\frac{b-1}{2}} · a^{\frac{b1}{2} } \text{,b为奇数} \end{cases}ab⎩⎨⎧1aa2b⋅a2ba2b−1⋅a2b1,b0,b1,b为偶数,b为奇数
快速幂方法扩底降幂方法
程序代码
import java.util.Scanner;public class KuaiSuMi {public static void main(String[] args) {Scanner sc new Scanner(System.in);while(sc.hasNext()) {int asc.nextInt();int bsc.nextInt();int p131;//计算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 i1;ib;i) ans ans*a;return ans;}public static int funtion2(int a,int b) {if(b0) return 1;if(b1) return a;if(b%20) return funtion2(a, b/2)*funtion2(a, b/2);else return funtion2(a, (b-1)/2)*funtion2(a, (b1)/2);}public static int funtion3(int a,int b,int p) {int ans 1;for(int i1;ib;i) ans ans*a;return ans%p;}public static int funtion4(int a,int b,int p) {int ans 1;for(int i1;ib;i) ans (ans*a)%p;return ans%p;}public static int funtion5(int a,int b,int p) {int ans 1;while(b0) {if(b%20) {aa*a%p;//扩底bb/2;//降幂} else {bb-1;ansans*a%p;aa*a%p;//扩底bb/2;//降幂}}return ans;}public static int funtion6(int a,int b,int p) {int ans 1;while(b0) {if(b%21) ansans*a%p;aa*a%p;//扩底bb/2;//降幂}return ans;}public static int funtion7(int a,int b,int p) {int ans 1;while(b0) {if((b1)!0) ansans*a%p;aa*a%p;//扩底bb1;//降幂}return ans;}
}
