求解线性同余方程

$$x\equiv r_1(mod{a}_1)$$

$$x\equiv r_2(mod{a}_2)$$

$$\dots$$

$$x\equiv r_k(mod{a}_k)$$

方法一： $x\equiv r_1(mod{a}_1)⟶x=r_1+a_1{y}_1$ $x\equiv r_2(mod{a}_2)⟶x=r_2+a_2{y}_2$ 联立：$a_1{y}_1-a_2{y}_2=r_2-r_1$ 求得：$y_1$的一个解 $y^{\prime }$，$y_1=y^{\prime }+k\frac{a_2}{gcd(a_1,a_2)}$ 带入原式：$x=r_1+a_1(y^{\prime }+k\frac{a_2}{gcd(a_1,a_2)})$ 化简：$x=r_1+a_1{y}^{\prime }+k\frac{a_1{a}_2}{gcd(a_1,a_2)}$

再化简得到：$x\equiv r_1+a_1{y}^{\prime }(mod\frac{a_1{a}_2}{gcd(a_1,a_2)})$ 这样就可以继续与后面的式子联立了

ll solve(ll *a,ll *r,ll n) { ll a1=a[1],r1=r[1]; for(int i=2;i<=n;++i) { ll a2=a[i],r2=r[i]; ll A=a1,B=a2,M=r2-r1,X,Y; ll GCD=exgcd(A,B,X,Y); if(M%GCD!=0) return -1; ll b1=a2/GCD; X=(X*M/GCD%b1+b1)%b1; r1=r1+a1*X; a1=a1*a2/GCD; } return r1; }

方法二：中国剩余定理 假设已经求出了前k-1个方程的解，现在联立第k个求解 $LCM={\prod }_{i=1}^{k-1}{a}_i$，前面的解为$x_{k-1}$。我们需要求出$t$，满足下面的式子 $x_{k-1}+t\times LCM\equiv r_k(mod{a}_k)$ 求出 $t$ 之后，得到一个新的解$x_k=x_{k-1}+t\times LCM$ 把LCM更新后，再取模

ll excrt(ll *a,ll *r,ll n) { ll LCM=a[1],ans=r[1]; for(int i=2;i<=n;i++) { ll A=LCM,B=a[i],M=(r[i]-ans%B+B)%B,X,Y; ll GCD=exgcd(A,B,X,Y); if(M%GCD!=0) return -1; ll b1=B/GCD; X=(X*(M/GCD)%b1+b1)%b1; ans+=X*LCM; LCM*=b1; ans=(ans%LCM+LCM)%LCM; } return ans; }

Strange Way to Express Integers POJ - 2891

#include <iostream> #include <algorithm> #include <cstdio> #define ll long long using namespace std; const int maxn=1e5+5,INF=0x3f3f3f3f; int n; ll a[maxn],r[maxn]; ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } ll q=exgcd(b,a%b,y,x); y-=a/b*x; return q; } ll excrt(ll *a,ll *r,ll n) { ll LCM=a[1],ans=r[1]; for(int i=2;i<=n;i++) { ll A=LCM,B=a[i],M=(r[i]-ans%B+B)%B,X,Y; ll GCD=exgcd(A,B,X,Y); if(M%GCD!=0) return -1; ll b1=B/GCD; X=(X*(M/GCD)%b1+b1)%b1; ans+=X*LCM; LCM*=b1; ans=(ans%LCM+LCM)%LCM; } return ans; } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;++i) scanf("%lld%lld",&a[i],&r[i]); ll ans=excrt(a,r,n); printf("%lld\n",ans); } return 0; }