同余,数论中很毒瘤重要的部分
接下来我将主要介绍如何求解线性同余方程组
两两相消法
形如
$ \left\{ \begin{aligned} x≡a_1(\mod{m_1})\\ x≡a_2(\mod{m_2})\\ \cdots\\ x=a_n(\mod{m_n})\\ \end{aligned} \right. $
的线性同余方程组,考虑先看俩
把(第四声)
$
\left\{
\begin{aligned}
x≡a_1(\mod{m_1})\\
x≡a_2(\mod{m_2})\\
\end{aligned}
\right.
$
转化为
$
\left\{
\begin{aligned}
x+m_1k_1=a_1\\
x+m_2k_2=a_2\\
\end{aligned}
\right.
$
则得到
$a_1-m_1k_1=a_2-m_2k_2$
则
$m_1k_1-m_2k_2=a_1-a_2$
则有解的等价条件为
$\gcd(m_1,m_2) | (a_1-a_2)$
用一元线性同余方程解法解出 $k_1$ 的一个特解 $k^\prime$,于是通解就为:
$k_1=k^\prime+\frac{cm_2}{\gcd(m_1,m_2)},c\in{N}$
代入 $x+m_1k_1=a_1$ :
$x=a_1-m_1k^\prime+\frac{cm_1m_2}{\gcd(m_1,m_2)}$
转换为
$x≡a_1-m_1k^\prime(\mod{\operatorname{lcm(m_1,m_2)}})$
接下来,依次合并即可得到最终解
$C++$
inline int Mod(int a[],int m[],int n){
int a1=a[0],a2,m1=m[0],m2,k1,k,d;
for(int i=1;i<n;i++){
a2=a[i],m2=m[i];
int k2,tmp;
exgcd(m1,m2,d,k1,k2);//扩展欧几里得
if((a2-a1)%d) return -1;//无解
tmp=m2/d;
k1=(k1*(a2-a1)/d%tmp+tmp)%tmp;//特解k’,保证最小正数,是否为整数依题目
a1+=m1*k1;
m1*=m2/d;
a1=(a1+m1)%m1;
}
return a1;//通解是a1+cm1,c是整数
}
别急着走,还有另一种解法
CRT(中国剩余定理)
CRT应用范围没那么广,主要因为其前置条件
那么既然他需要条件,我们就给他条件
假定 $a_1~a_n$ 互素,求解关于 $x$ 的同余方程组。
$ \left\{ \begin{aligned} x≡b_1(\mod{a_1})\\ x≡b_2(\mod{a_2})\\ \cdots\\ x=b_n(\mod{a_n})\\ \end{aligned} \right. $
根据中国剩余定理
$a_1,a_2 \cdots a_n$ 互素时
有模 $A=a_1,a_2 \cdots a_n$ 的唯一解。
令 $A_i=A/a_i$ ,由互素,知 $\gcd(A_i,a_i)=1$
又 $A_i·A^{-1}_i≡1(\mod{m_i})$
则通解为
$cA+\sum^{n}_{i=1}a_iA_iA^{-1}_i$
$C++$
//数组从0标号
ll CRT(int a[],int m[],int n){
ll M=1ll,ans=0;
for(int i=0;i<n;i++) M*=m[i];
for(int i=0;i<n;i++) ans=(ans+a[i]*M%M*inv(M)%M)%M;//矩阵求逆
return ans;
}
附
·例题 扩展中国剩余定理
·例题 曹冲养猪(这题AcWing提高课也有,而且Y总讲的不错)
核心代码(俩题都一样):
$C++$
#define F(i,a,b) for(int i=a;i<=b;i++)
typedef __int128 ll;
const int N=1e5+10;
ll x,y,d;
int n;
inline void exgcd(ll &x,ll &y,ll a,ll b){
if(!b) d=a,x=1,y=0;
else exgcd(y,x,b,a%b),y-=a/b*x;
}
inline ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
inline ll lcm(ll a, ll b){
return a/gcd(a,b)*b;
}
ll a,b,A,B;
void merge(){
exgcd(x,y,a,A);
ll c=B-b;
if(c%d) puts("-1"),exit(0);
x=x*c/d%(A/d);
if(x<0) x+=A/d;
ll mod=lcm(a, A);
b=(a*x+b)%mod;
if(b<0) b+=mod;
a=mod;
}