逆元：
方程 ax≡1(mod p) 的解称为a关于模p的逆，当gcd(a,p)==1（即a，p互质）时，方程有唯一解，否则无解。
也就是说一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在 。
有
(a+b)%c=(a%c+b%c)%c
(a*b)%c=(a%c*b%c)%c
(a-b)%c=(a%c-b%c)%c
但是却没有 (a/b)%c=(a%c/b%c)%c ， 这是错的 ， 但是我们可以将它转化成乘法。
令inv(x)表示的是某个数的逆元。
那么该式就可以改成 ( a / b ) % c = ( a * inv(b) ）% c = ( a % m * inv(b) % m ) % m;
1.用扩展欧几里得求逆元
咳咳。。。为什么要用扩展欧几里得求逆元？
（ 什么是扩展欧几里得？
啊哈哈哈哈~~~不会就看下面这俩链接吧 ， 应该就懂了 。。。。
扩展欧几里得2 开玩笑~ ）
a * y ≡ 1 ( mod m ) 等价于 ：a * y = 1 + m * k
a * y = 1 + m * k 等价于 ：a * y – m * k = 1 该式子 可以用
欧几里得扩展 来求但是 必须要满足： gcd（a，m）=1；
//扩展欧几里得法求逆元
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll ExEculid(ll a , ll b , ll &x , ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll tx , ty;
ll d = ExEculid(b , a % b , tx , ty);
x = ty;
y = tx - (a/b)*ty;
return d;
}
ll inv(ll a , ll n)//模 n 下 a 的逆元
{
ll x , y;
ll d = ExEculid(a , n , x , y);//必要条件 gcd(a , n) = 1;
return d == 1 ? (x + n) % n : -1;//无则返回-1
//(x + n) % n 这样写的原因是防止x为负数
}
int main()
{
int a , n;
while(cin >> a >> n)
cout << inv(a , n) << endl;
return 0 ;
} 2 . 用费马小定理求逆元
什么是费马小定理？？
假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）
看到这样一个式子是不是可以很容易想到 a * a^(p-2) ≡ 1（mod p） ， 那么a ^(p-2) 就是模p下 a 的逆元了。
推导过程：
如果这个数很大很大自然可以想到用快速幂来求解a ^(p-2)
下面代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll qpow(ll a , ll b , ll m)//快速幂
{
ll ans = 1;
a %= m;
while(b)
{
if(b & 1)
{
ans = ans * a % m;
}
a = a * a % m;
b = b / 2;
}
return ans;
}
ll Fermat(ll a , ll p)//费马小定理求 a ^(p-2)
{
return qpow(a , p-2 , p);
}
int main()
{
ll a , b;
cin >> a >> b;
cout << Fermat(a , b) << endl;
return 0;
} 例子！！一看就懂！！！
如果还是不太懂逆元是怎么一回事 ， 可以看看这个例子：
很明显看出（18 / 3）% 5 的答案是 1。
但是如果前面的数不是18 而是一个很大很大的数的连longlong都存不下呢？
我们肯定是一边乘一边求mod。
首先可以将这个式子转变为（18 % 5 * inv(3) % 5 ) % 5.
费马小定理： inv(3) = 3 ^ (5 - 2) = 27 ===》(3 * 27 ) % 5 = 1.
扩展欧几里得：inv(3) = ExEculid( 3 ,5 , x , y) 中 x 的值 ， 这里x = 2 ===》( 3 * 2 ) % 5 = 1.
这样就结束了~ 所以好像说了这么多 ， 其实就只是为了实现除法的同余解法
但是！！！
上面俩个方法求逆元的前提条件是 P 是素数 或者 a , p 互质 ， 那如果p是任意取的数怎么办呢？
这时候就要引入欧拉定理啦~~
我们来看看欧拉定理是讲什么的：
欧拉定理：对于正整数N，代表小于等于N的与N互质的数的个数，记作φ(N)
φ(N)的求解有这样几个方法（在此直接写结论 ， 不再证明）：
1.如果n为某一个素数p，则φ(p)=p-1;
比如 p = 7 , 那么φ(7) = 6 （1 ， 2 ， 3 ， 4 ， 5 ，6 ）;
2. 1 与任何数都互质
3.如果 n 可以分为俩个互质数的积 ， 那么φ(n)=φ(a)*φ(b)；
例如：φ(56)=φ(7)*φ(8) = 6 * 4 = 24；
4.如果 n 为某个质数的次方（例：n = p ^ k）则有公式： φ(n) = p^k - p^(k-1)
例如：φ(8) = 2^3 - 2^2 = 4;
利用容斥定理
如果 n 不是质数 ， 则只需要除去 n 的质因子及 质因子的倍数
例：φ(10) = φ(2) * φ(5)
1 2 3 4 5 6 7 8 9
no no no no no
φ(10) = 4 (1 , 3 , 7 , 9);
说是一个逆元最常见问题 ， 求如下表达式的值（已知
这题可以用扩展欧几里得和费马小定理来解决 ， 但是 ， 必须保证 a , m 互质才行 ， 因而我们有这样一个式子 ，
不区分互不互素
证明如下：
京公网安备 11010502036488号