数学-中国剩余定理及乘法逆元

noCc0PDaQQH

中国剩余定理及乘法逆元

叠甲：本文参照了 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;} 这里要求 \(\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\)。
  

实现

#include <bits/stdc++.h>#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<int,int> #define mkp(x,y) make_pair(x,y);#define clearArray(name,sum,sta,endd) for(int i=sta;i<=endd;i++) name=sum#define gcd(a,b) __gcd(a,b)#define lcm(a,b) (a*b)/__gcd(a,b)#define add(x,y) (((x+y)%mod+mod)%mod)#define mul(x,y) (x%mod*y%mod)#define INF 1000000007 #define mod 998244353int qpow(int x,int a){int ans=1;while(a){if(a&1)ans=(ans*x);x=(x*x);a>>=1;}return ans;}using namespace std;#define maxn 100//vector <pii >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 <= n;i ++)         {                cin>>a>>b;                ans *= a;        }        for(int i = 1;i <= n;i ++)         {                int k = ans / a;                int x , y;                exgcd(k , a , x , y);                __int128 sum=((__int128)k * b * x % ans);                s += (int)sum % ans;        }        cout<<((s % ans + ans) % ans);        return 0;}