快速幂求逆元-C语言

快速幂求逆元

算法描述

快速幂求逆元是指对于一个数 $a$ 和一个质数 $p$，求 $a^p$ 的逆元，即 $a^{-1}$。

算法步骤

1. 首先判断 $a$ 是否为 $p$ 的倍数，若是，则不存在逆元，输出 “impossible”。
2. 若 $a$ 不为 $p$ 的倍数，则利用快速幂求 $a^p$ 的逆元。
3. 设 $a^p=a_p$，则 $a^{-1}=a_p^{-1}\cdot p$。
4. 利用快速幂求 $a_p^{-1}$ 的逆元，即 $a_p^{-1}=a_p^{p-2}$。
5. 最后，输出 $a^{-1}=a_p^{-1}\cdot p$。

复杂度分析

• 时间复杂度：$O(\log p)$，其中 $p$ 为质数。
• 空间复杂度：$O(1)$。

代码实现

#include <stdio.h>
typedef long long LL;

LL quick_exponent(LL a, LL b, LL mod) {
    LL ans = 1;
    
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    
    return ans;
}

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

输入输出样例

输入：
3
2 3
3 5
10 7


输出：
impossible
5
1

注意事项

• 对于 $a$ 为 $p$ 的倍数的情况，输出 “impossible”。
• 对于 $a$ 不为 $p$ 的倍数的情况，输出 $a^{-1}$。