給定 \(n\) 個同余模方程
\[\left\{\begin{aligned} x\equiv\, & m_1(mod\quad a_1)\\ x\equiv\, & m_2(mod\quad a_2)\\ &\vdots\\ x\equiv\, & m_n(mod\quad a_n) \end{aligned} \right. \]不保證 \(gcd(m_i,m_j)=1(i\neq j)\) ,求最小的正整數解 \(x\)
2個方程的解
因為兩兩之間不互質，所以不能通過ex_gcd求解
嘗試將問題縮小到兩個方程，再逐步推出最后的解，有
也就等同于 \(\exists k_1,k_2\) ，使得
\[\left \{ \begin{aligned} x=&\,k_1a_1+m_1\\ x=&\,k_2a_2+m_2 \end{aligned} \right.\tag{1} \]即有
\[k_1a_1+m_1=k_2a_2+m_2 \]整理可得
\[k_1a_1-k_2a_2=m_2-m_1 \]此時可用ex_gcd求解 \(k_1,k_2\) ，有解的充要條件是： \(gcd(a1,-a2)\mid(m_2-m_1)\)
記 \(d=gcd(a1,-a2)\),且 \(\exists k_1^{'},k_2^{'}\) ,使得
可以通過ex_gcd求解得出 \(k_1^{'},k_1^{'}\)的特解，設 \(t=\frac{m_2-m_1}{d}\),則
通解形式為（ \(k\) 為任意整數）
\[\left \{ \begin{aligned} k_1&=k_1^{'}t+k\frac{-a_2}{d}\\&=k_1+k\frac{-a_2}{d}\\ k_2&=k_2^{'}t-k\frac{a_1}{d}\\&=k_2-k\frac{a_1}{d}\\ \end{aligned} \right. \]再把 \(k_1\) 的通解帶入到 \(x=k_1a_1+m_1\) 中
\[\begin{aligned} x&=(k_1+k\frac{-a_2}{d})a_1+m_1\\ &=k_1a_1+k\frac{a_1(-a_2)}{d}+m_1\\ &=k\frac{a_1(-a_2)}{d}+k_1a_1+m_1\\ &=\underbrace{k}_{k_1}\underbrace{lcm(a_1,-a_2)}_{a_1}+\underbrace{k_1a_1+m_1}_{m_1} \end{aligned} \]這樣就得到了新的
\[\left \{ \begin{aligned} k_1&=k\quad\\ a_1&=lcm(a_1,-a_2)\\ m_1&=k_1a_1+m_1\\ \end{aligned} \right. \]與一開始方程組 \((1)\) 中的表達形式相同，這樣就將兩個方程合并成了一個方程
\[x=k_1a_1+m_1\tag{2} \]此時 \(x\) 的解就是 \(m_1\) 在模 \(a_1\) 下的最小正整數解
n個方程的解
經過 \(n-1\) 輪整合，可以把 \(n\) 個方程合并成為一個方程
\[x=ka+m \]最終的結果就是
\[x=(m\%a+a)\%a \]例題
204. 表達整數的奇怪方式
- 每一輪合并得出的方程 \((2)\) 的 \(k_1\) 都保證是最小正整數解，這樣得到新的 \(m_1\) 是最小正整數解，以防在計算程序中溢位
- 保證最后的最小正解，模數也應當為正
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x=1;
y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main() {
int n;
scanf("%d",&n);
ll a1,m1;
scanf("%lld%lld",&a1,&m1);
bool flag=true;
for(int i=0;i<n-1;++i) {
ll a2,m2;
scanf("%lld%lld",&a2,&m2);
a2=-a2;
ll k1,k2;
ll d=exgcd(a1,a2,k1,k2);
if((m2-m1)%d) {
flag=false;
break;
}
k1=k1*((m2-m1)/d);//特解
ll temp=abs(a2/d);
k1=(k1%temp+temp)%temp;//通解中保證最小正整數解
m1=k1*a1+m1;
a1=a1/d*a2;
}
if(flag) {
if(a1<0) a1=-a1;
m1=(m1%a1+a1)%a1;//保證最后的最小正解，模數也應當為正
printf("%lld",m1);
} else puts("-1");
return 0;
}
參考
- 演算法講堂[基礎]-數論基礎定理與演算法
- https://www.acwing.com/activity/content/code/content/53307/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279204.html
標籤：其他
上一篇：二叉樹的重建
下一篇：《劍指offer》刷題筆記