Acwing---875. 快速幂

本文主要是介绍Acwing---875. 快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题目

给定 $n$ 组 $ai$,$bi$,$pi$，对于每组数据，求出 a^bii $mod$ pi 的值。

输入格式
第一行包含整数 $n$。

接下来 $n$ 行，每行包含三个整数 $ai$,$bi$,$pi$。

输出格式
对于每组数据，输出一个结果，表示 a^bii $mod$ pi 的值。

每个结果占一行。

数据范围
$1\le n\le 100000,$

$1\le ai,bi,pi\le 2\times 10^9$

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

2.基本思想

快速幂解法 O(n∗logb)

基本思路:

注意:

• b & 1就是判断b的二进制表示中第0位上的数是否为1,若为1,b&1=true,反之b&1=false
• b & 1也可以用来判断奇数和偶数,b&1=true时为奇数,反之b&1=false时为偶数

3.代码实现

import java.util.Scanner;public class Main {static long res;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();while (n-- > 0) {long ai = sc.nextInt(), bi = sc.nextInt(), pi = sc.nextInt();pmi(ai, bi, pi);}}private static void pmi(long ai, long bi, long pi) {res = 1;while (bi != 0) {//最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。if (bi % 2 == 1) res = res * ai % pi;bi /= 2;ai = ai * ai % pi;}System.out.println(res % pi);}
}

这篇关于Acwing---875. 快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---