java 快速幂取模
时间: 2023-11-20 21:54:09 浏览: 55
Java中的快速幂取模是一种计算幂取模的算法,它可以在不使用大量乘法的情况下快速计算出幂取模的结果。这种算法使用二进制分解来计算幂,将幂分解为2的幂次方的和,然后使用模运算来计算每个2的幂次方的结果,最后将这些结果相乘得到最终结果。Java中的快速幂取模可以用于计算大数的幂取模、最大公约数、乘法逆元、素数判定以及大素数的生成等问题。
快速幂取模的实现需要用到以下两个公式:
1. a^b mod c = (a mod c)^b mod c
2. a^(2n) mod c = (a^n mod c)^2 mod c
Java中的快速幂取模的实现可以参考以下代码:
```
/**
* 快速幂取模
* @param one 底数
* @param two 指数
* @param mod 模
* @return 结果
*/
public static String Power(String one,String two,String mod) {
if(two.equals("0")) { //0次幂结果为1
return "1";
}else if(two.equals("1")){ //1次幂结果为它本身
return Mod(one, mod);
}
String count=two,result="1",temp=one;
while(!count.equals("0")){
if(Mod(count, "2").equals("1")) //看它二进制最后一位是不是1
result=Multiply(result, temp, mod);
if(!count.equals("1")) //这里避免最后一次做没用的乘法
temp=Multiply(temp, temp, mod);
count=Division(count, "2"); //次数减1,相当于二进制右移一位
}
return result;
}
```