题目描述:
输入b,p,k的值,求b^p mod k的值。其中b,p,k×k为长整型数。
解题思路:
- 如果指数为奇数,那么结果乘以当前的底数,指数除以2(整除运算)。
- 如果指数为偶数,那么底数变为原来底数的平方,指数除以2。
代码:
分治算法
package lanqiao;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long b = sc.nextInt();
long p = sc.nextInt();
long k = sc.nextInt();
System.out.println(b + "^" + p + " mod " + k + "=" + f(b,p,k));
}
public static long f(long b,long p,long k)
{
long ans = 1;
while(p > 0)
{
if(p % 2 == 1)
ans = ans * b % k;
b = b * b % k;
p /= 2;
}
return ans;
}
}
标签:题目,底数,long,2154,nextInt,ans,sc,取余,public
From: https://blog.csdn.net/weixin_64443786/article/details/136633129