• 欢迎光临~

快速幂求逆元

开发技术 开发技术 2022-07-23 次浏览

快速幂求逆元

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

注意:请返回在 $ 0 sim p-1 $ 之间的逆元。

乘法逆元的定义

若整数 $ b,m $ 互质,并且对于任意的整数 $ a $,如果满足 $ b|a $,则存在一个整数 $ x $,使得 $ a/b≡a times x pmod m $,则称 $ x $ 为 $ b $ 的模 $ m $ 乘法逆元,记为 $ b^{-1} pmod m (。 ) b $ 存在乘法逆元的充要条件是 $ b $ 与模数 $ m $ 互质。当模数 $ m $ 为质数时,$ b^{m-2} $ 即为 $ b $ 的乘法逆元。

想法

题目中说了$ p_i $ 是质数
可以通过快速幂算出来逆元

思路

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

证明:

[a / b equiv a times x pmod m ]

[a / b equiv a times b^{-1} pmod m ]

[frac{1}{b} equiv b^{-1} pmod m ]

[1 equiv b^{-1} times b pmod m ]

[b^{-1} times b equiv 1pmod m ]

根据费马小定理

(如果p是一个质数,而整数a不是p的倍数,则有a^{p-1}≡1pmod p)

故$$b^{m-1}≡1pmod m$$

[b times b^{m-2} equiv 1pmod m ]

[b times b^{m-2} equiv b^{-1} times b equiv 1pmod m ]

[b times b^{m-2}= b^{-1} times b ]

[b^{-1}=b^{m-2} ]

[x = b^{m-2} ]

所以

  1. (b)(m)互质的时候,逆元为(b^{m-2})

  2. (b)(m)不互质(即(b)(m)的倍数)的时候,逆元不存在

(b times x % m = 0)

(x)无论多少(b)都有因数(m),因此逆元不存在

码来!

#include <iostream>
using namespace std;
typedef long long LL;

LL quickPow(int a, int b, int p)
{
    LL res = 1 % p;
    
    while(b)
    {
        if(b & 1) res = res * a % p;
        
        b >>= 1;
        
        a = a * (LL)a % p;
    }
    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("%dn", quickPow(a, p - 2, p));
        
    }
    return 0;
}

注意:快速幂算法只有当(p)是质数是才可以使用

程序员灯塔
转载请注明原文链接:快速幂求逆元
喜欢 (0)