4、快速幂

AcWing 875. 快速幂

AcWing 876. 快速幂求逆元

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int fast_mi(int a, int b, int c) {
        long[] mis = new long[32];
        for (int i = 0; i < 32; i++) {
            if (i == 0)
                mis[i] = a%c;
            else {
                mis[i] = mis[i - 1]*mis[i - 1]%c;
            }
        }
        long sum=1;
        for (int i = 31; i >= 0; i--) {
            if((b>>i&1)!=0){
                sum*=mis[i];
                sum%=c;
            }
        }
        return (int) (sum%c);
    }

    void init() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            int num=fast_mi(a, b, c);
            System.out.println(num);
        }
    }
}

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


LL qmi(int a, int b, int p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}