什么是逆元
来自一个大佬的解释，反正我是看懂了。。
乘法逆元：
- 模p意义下，一个数a如果有逆元x，那么除以a相当于乘以x。
- 在模n的意义下，a存在逆元的充要条件是**n不等于1，且（a，n）互质。
怎样求逆元？
-
费马小定理（有限制）
=》p为素数时，a关于mod p的逆元为a^(p-2)mod p。用快速幂模。 -
扩展欧几里得算法（普遍适用）
一篇解释了推导过程的博客
- 给定模数n，求a的逆元
- 即ax=1(mod n)
- =》ax-ny=1
- 所以可用扩展欧几里得， ax+by=gcd（a，b）求逆元，即求x的值。
-
注意：
存在逆元的判断条件是
a，m互质。
if(gcd(a,m) != 1) //a，m不互质，则不存在逆元
cout << "Not Exist" << endl;
else
{
ext_gcd(a, m, x, y);
LL ans = (x<=0) ? (x%m+m) : x; //有可能x是负数，x要先取模再加
cout << ans << endl;
看一道题 hdu 1576
- 题意：给出n(n=A%9973)，求(A/B)%9973。(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
-
思路：
用乘法逆元的定义:模p意义下，一个数a如果有逆元x，那么除以a相当于乘以x。即变成(A/inv(B))%9973，即(A%9973/inv(B)%9973)%9973。
所以这道题就是求inv(B)，求B的逆元。 - 上代码，两种方法都有了
#include <iostream>
#include <cstdio>
#define N 9973
using namespace std;
typedef long long LL;
LL power(LL a, int b, int p) //要用long long啊啊
{///快速幂模，p为素数时，a关于mod p的逆元为a^(p-2)mod p
LL ans = 1; //要用long long啊啊
while(b > 0)
{
if(b&1) //a是奇数
ans = ans*a%p;
b >>= 1;
a = a*a%p;
}
return ans%p;
}
LL ext_gcd(int a, int b, int &x, int &y)
{///扩展欧几里得求逆元，普遍的求法
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int r = ext_gcd(b, a%b, x, y);
int temp = x; //扩展欧几里得的推导
x = y;
y = temp - a/b*y;
return r;
}
int main()
{
int t,x,y;
int n, b;
while(cin >> t)
{
while(t--) //注意看题！别总犯低级错误！
{
scanf("%d%d", &n, &b);
//cout << (n%N*power(b, N-2, N))%N << endl;
ext_gcd(b, N, x, y); //N不用加负号
if(x < 0) x += N; //要加模的数n，防止是负数
cout << (n%N*x%N)%N << endl;
}
}
return 0;
}
