题目描述
逆元的通俗理解:对于一个数a,我们想找到另一个数b使得a和b相乘之后对p取余的结果是1;
比如2 x 3 ≡ 1 (mod 5 ) 即 2 x 3 对 5 取模和 1 对 5 取模是同余的 都是1 。 其中 3就是 2的乘法逆元
快速幂求逆元思路(引自HZ)
当n为质数时,可以用快速幂求逆元:
a / b ≡ a * x (mod n)
两边同乘b可得 a ≡ a * b * x (mod n)
即 1 ≡ b * x (mod n)
同 b * x ≡ 1 (mod n)
由费马小定理可知,当n为质数时
b ^ (n - 1) ≡ 1 (mod n)
拆一个b出来可得 b * b ^ (n - 2) ≡ 1 (mod n)
故当n为质数时,b的乘法逆元 x = b ^ (n - 2)
需要注意的地方
不能用res判断是否应该输出impossible,因为当b=2,p=2时,此时的2的零次方也为1.
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
LL qmi(int a,int k,int p)
{
LL res=1;
while(k)
{
if(k&1) res=res*a%p;
k>>=1;
a=(LL)a*a%p;
}
return res;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,p;
scanf("%d%d",&a,&p);
if(a%p) printf("%d\n",qmi(a,p-2,p));
else printf("impossible\n");
}
return 0;
}