快速幂,龟速乘,逆元 | ShanTianQi's Blog

快速幂

例题：

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

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

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

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

每个结果占一行。

数据范围
1≤n≤100000
1≤ai,bi,pi≤2×10^9^

输入样例：
2
3 2 5
4 3 9
输出样例：
4
1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n -- > 0){
            long a = sc.nextLong();
            long b = sc.nextLong();
            long c = sc.nextLong();

            System.out.println(qki(a,b,c));
        }

        sc.close();
    }

    private static long qki(long a,long b,long p){
        long res = 1 % p;

        while (b > 0){
            if ((b & 1) == 1) res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }

        return res;
    }
}

龟速乘

例题：

求 a 乘 b 对 p 取模的值。

输入格式
第一行输入整数a，第二行输入整数b，第三行输入整数p。

输出格式
输出一个整数，表示a*b mod p的值。

数据范围
1≤a,b,p≤10^18^

输入样例：
3
4
5
输出样例：
2

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long p = sc.nextLong();

        long res = 0;

        while (b != 0){
            if ((b & 1) == 1) res = (res + a) % p;
            a = (a + a) % p;
            b >>= 1;
        }

        System.out.println(res);

        sc.close();
    }
}

逆元

首先了解三个定义：同余，费马小定理，欧拉定理

同余

定义：若整数a和整数b除以正整数m的余数相等，则称a,b模m同余，记为a ≡ b(mod m)

费马小定理

若p是质数，则对于任意整数a，有a^p^ ≡ a(mod p)

欧拉定理

若正整数a,n互质，则a^φ(n)^ ≡ 1(mod n)，其中φ(n)为欧拉函数

欧拉定理的推论

若正整数a,n互质，则对于任意正整数b，有a^b^ ≡ a^bmodφ(n)^(mod p)

乘法逆元

若整数b,m互质，并且b|a，则存在一个整数x，使得a/b ≡ a * x(mod m)。称x为b的模m乘法逆元，记为b^-1^(mod m)。

特别的，如果m为质数，并且b < p，根据费马小定理b^p-1^ ≡ 1(mod p)，即b * b^p-2^ ≡ 1(mod p)。因此当模数p为质数时，b^p-2^即为b的乘法逆元。

例题：

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

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

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

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

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

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

数据范围
1≤n≤10^5
1≤ai,pi≤2∗10^9^

输入样例：
3
4 3
8 5
6 3
输出样例：
1
2
impossible

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T -- > 0){
            int a = sc.nextInt();
            int p = sc.nextInt();
            long res = 1;

            if (a % p != 0){
                int k = p - 2;
                while (k != 0){
                    if ((k & 1) != 0) res = res * a % p;
                    k >>= 1;

                    a = (int)((long)a * a % p);//a * a小心爆int
                }
                System.out.println(res);
            }else System.out.println("impossible");
        }

        sc.close();
    }
}