IT评测·应用市场-qidao123.com

标题: 数学-中国剩余定理及乘法逆元 [打印本页]

---

作者: 篮之新喜    时间: 2025-3-10 14:25
标题: 数学-中国剩余定理及乘法逆元
中国剩余定理及乘法逆元

叠甲：本文参照了 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.扩展欧几里得

1. int exgcd(int a , int b , int &x , int &y)
2. {
3.         if(!b)
4.         {
5.                 x = 1;
6.                 y = 0;
7.                 return a;
8.         }
9.         int r = exgcd(b , a % b , x , y);
10.         int t = x;
11.         x = y;
12.         y = t - (a / b) * y;
13.         return r;//返回的是gcd(a,b)
14. }
15. int get_INV(int a,int p)
16. {
17.         int x,y;
18.         exgcd(a,p,x,y);
19.         return x;
20. }

复制代码

这里要求 \(\gcd(a,p)=1\)，扩展欧几里得法和求解线性同余方程是一个原理，在这里不睁开解释。
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

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4