C语言快速幂和快速幂求逆元

快速幂是一种用于快速计算一个数的整数次幂的算法，其时间复杂度为O(logn)。而快速幂求逆元是在模意义下，求一个数的乘法逆元的算法，其时间复杂度也为O(logn)。

以下是C语言实现快速幂和快速幂求逆元的代码：

1. 快速幂

#include <stdio.h>

typedef long long LL;

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

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}

2. 快速幂求逆元

#include <stdio.h>

typedef long long LL;

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

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int a, p;
        scanf("%d%d", &a, &p);
        int res = qmi(a, p - 2, p); // a^(p-2)
        if (a % p) printf("%d\n", res); // 不是倍数，输出结果
        else puts("impossible"); // 是倍数，不存在逆元
    }
    return 0;
}