数学-中国剩余定理及乘法逆元
中国剩余定理及乘法逆元叠甲：本文参照了 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;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,b,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;}
页:
[1]