【数论】快速幂

快速幂

给定 n 组 $a_i$,$b_i$,$p_i$，对于每组数据，求出 ${a_i}^{b_i}mod$ $p_i$ 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含三个整数 $a_i$,$b_i$,$p_i$。

输出格式

对于每组数据，输出一个结果，表示 ${a_i}^{b_i}mod$ $p_i$的值。

每个结果占一行。

数据范围

1≤n≤100000,
1≤$a_i$,$b_i$,$p_i$≤2×$10^9$

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

【思路分析】

如果使用朴素算法要进行b次乘积运算，因此朴素算法的时间复杂度是O(b)的

但是使用快速幂算法即可将时间复杂度优化为logb的

快速幂的思路如下

对于一个数 $a^b$ 我们可以先将

$a^{2^0}$ mod p

$a^{2^1}$ mod p

$a^{2^2}$ mod p

…

$a^{2^{logb}}$ mod p

预处理出来

而且可以发现$a^i$ = $a^{i-1}$ * $a^{i-1}$ mod p

然后$a^b$ 就可以用预处理出来的数来表示

例如b的二进制是101101

则$a^{45}$ = $a^{2^0}$ * $a^{2^2}$ * $a^{2^3}$ * $a^{2^5}$

代码如下

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int n = Integer.parseInt(br.readLine());
        while(n-- > 0) {
            String[] data = br.readLine().split(" ");
            int a = Integer.parseInt(data[0]);
            int b = Integer.parseInt(data[1]);
            int p = Integer.parseInt(data[2]);
            pw.println(function((long)a, b, p));
        }
        br.close();
        pw.close();
    }
    //求快速幂 a^b % p
    public static long function(long a, int b, int p) {
        long res = 1 % p;
        while(b > 0) {
            //如果b的末位是1
            if((b & 1) == 1) {
                res = res * a % p;
            }
            //a的计算可以通过上一次的a求出
            a = a * a % p;
            //b右移一位
            b >>= 1;
        }
        return res;
    }
}

快速幂的应用：求逆元

给定 n 组 $a_i$,$p_i$，其中 $p_i$ 是质数，求 $a_i$ 模 $p_i$的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 0∼p−1之间的逆元。

乘法逆元的定义

若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 $\frac{a}{b}$ ≡ a×$x$(mod m)，则称 $x$ 为b 的模 m 乘法逆元，记为 $b^{-1}$ (mod m) 。

b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，$b^{m-2}$ 即为 b 的乘法逆元。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个数组 $a_i$,$p_i$，数据保证 $p_i$ 是质数。

输出格式

输出共 n 行，每组数据输出一个结果，每个结果占一行。

若 $a_i$ 模 $p_i$ 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。

数据范围

1≤n≤$10^5$,
1≤$a_i$,$p_i$≤2∗$10^9$

输入样例：

3
4 3
8 5
6 3

输出样例：

1
2
impossible

费马小定理(可以通过欧拉函数推出)

费马小定理表述为：若 p 是质数，且整数 a 与 p 互质（即 gcd(a,p)=1，gcd表示最大公约数 ），那么有$a^{p-1}$ ≡ 1 (mod p) 。

推导乘法逆元公式

已知乘法逆元的定义：对于整数 a 和质数 p ，若存在整数 x ，使得 ax ≡ 1 (mod p) ，则 x 是 a 模 p 的乘法逆元。 由费马小定理$a^{p-1}$ ≡ 1 (mod p) ，等式两边同时除以 a （因为 a 与 p 互质，所以可以除 ），得到 $a^{p-2}$ ≡ $\frac{1}{a}$ (mod p) 。 也就是说，当 p 是质数且 a 与 p 互质时，a 模 p 的乘法逆元就是 $a^{p-2}$ mod p。

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int n = Integer.parseInt(br.readLine());
        while(n-- > 0) {
            String[] data = br.readLine().split(" ");
            int a = Integer.parseInt(data[0]);
            int p = Integer.parseInt(data[1]);
            //如果a是p的倍数，则一定没有逆元
            if(a % p == 0) {
                pw.println("impossible");
            } else {
                pw.println(function((long)a, p - 2, p));
            }
        }
        br.close();
        pw.close();
    }
    //求快速幂 a^b % p
    public static long function(long a, int b, int p) {
        long res = 1 % p;
        while(b > 0) {
            if((b & 1) == 1) {
                res = res * a % p;
            }
            a = a * a % p;
            b >>= 1;
        }
        return res;
    }
}