中国剩余定理及乘法逆元
叠甲：本文参照了 OI-wiki 并提出了自己的理解
乘法逆元
什么是乘法逆元
已知 \(a,p\)，求 $a \times b \mod p =1 $ 的解，全部 \(\mod p\) 都相等的解被视为一个解。
这就是乘法逆元，\(b\) 通常称之为：模 \(a\) 意义下的乘法逆元。偶然候也记作 \(a^{-1}\)。
简单来说（即定义），如果一个线性同余方程 \(ax \equiv 1 \pmod b\)，则 \(x\) 称为 \(a \bmod b\) 的逆元，记作 \(a^{-1}\)。
解法
1.扩展欧几里得
- int exgcd(int a , int b , int &x , int &y)
- {
- if(!b)
- {
- x = 1;
- y = 0;
- return a;
- }
- int r = exgcd(b , a % b , x , y);
- int t = x;
- x = y;
- y = t - (a / b) * y;
- return r;//返回的是gcd(a,b)
- }
- int get_INV(int a,int p)
- {
- int x,y;
- exgcd(a,p,x,y);
- return x;
- }
2.快速幂法
由于 \(ax \equiv 1 \pmod b\)；
以是 \(ax \equiv a^{b-1} \pmod b\)（根据费马小定理)；
以是 \(x \equiv a^{b-2} \pmod b\)。
然后我们就可以用快速幂来求了。
由于根据了费马小定理，以是这里要求 \(p\) 是质数。
中国剩余定理 (Chinese Remainder Theorem, CRT)
什么是CRT
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
即求满足以下条件的整数：除以 \(3\) 余 \(2\)，除以 \(5\) 余 \(3\)，除以 \(7\) 余 \(2\)。被称为中国剩余定理。
中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 \(n_1, n_2, \cdots, n_k\) 两两互质）：
\[\begin{cases}x &\equiv a_1 \pmod {n_1} \\x &\equiv a_2 \pmod {n_2} \\ &\vdots \\x &\equiv a_k \pmod {n_k} \\\end{cases}\]
解法
- 计算全部模数的积 \(n\)；
- 对于第 \(i\) 个方程：
- 计算 \(m_i=\frac{n}{n_i}\)；
- 计算 \(m_i\) 在模 \(n_i\) 意义下的逆元 \(x\)；
- 计算 \(c_i=m_ix\)（不要对 \(n_i\) 取模，否则根据定义 \(m_ix \mod n_i =1\)）。
- 方程组在模 \(n\) 意义下的唯一解为：\(x=\sum_{i=1}^k a_ic_i \pmod n\)。
实现
[code]#include #define fre(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)#define tesin(x) freopen(x ".in", "r", stdin)#define fastread ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define int long long#define ull unsigned long long #define pii pair #define mkp(x,y) make_pair(x,y);#define clearArray(name,sum,sta,endd) for(int i=sta;i>=1;}return ans;}using namespace std;#define maxn 100//vector e[maxn];int exgcd(int a , int b , int &x , int &y) { if(!b) { x = 1; y = 0; return a; } int r = exgcd(b , a % b , x , y); int t = x; x = y; y = t - (a / b) * y; return r;}int n,a[maxn],b[maxn],ans=1,s;signed main(){ cin>>n; int ans = 1; for(int i = 1;i >a>>b; ans *= a; } for(int i = 1;i |
