逆元
1、思路
(1)当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)
(2)当n不是质数时，可以用扩展欧几里得算法求逆元：
a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1假设a的逆元为x，那么有a * x ≡ 1 (mod p)
等价：ax + py = 1
exgcd(a, p, x, y)
快速幂求逆元代码模板：
#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;
a=(ll)a*a%p;
k>>=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",qmi(a,p-2,p));
}
return 0;
}
扩展欧几里得算法求逆元代码模板:
#include <iostream>
using namespace std;
typedef long long ll;
int n;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
scanf("%d",&n);
while(n--)
{
int a,p,x,y;
// if (a < p) swap(a, p);
scanf("%d %d",&a,&p);
int d=exgcd(a,p,x,y);
if(d == 1)
printf("%d",(ll)x+p)%p);//保证x是正数
else
puts("impossible");
}
return 0;
}
查看3道真题和解析