转载：/**********************一般模线性方程组***********************/同样是求这个东西。。X mod m1=r1X mod m2=r2.........X mod mn=rn首先，我们看两个式子的情况X mod m1=r1……………………………………………………………(1)X mod m2=r2……………………………………………………………(2)则有 X=m1*k1+r1………………………………………………………………(*)X=m2*k2+r2那么 m1*k1+r1=m2*k2+r2整理，得m1*k1-m2*k2=r2-r1令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1)，原式变成ax+by=m熟悉吧？此时，因为GCD(a,b)=1不一定成立，GCD(a,b) | m 也就不一定成立。所以应该先判 若 GCD(a,b) | m 不成立，则！！！方程无解！！！。否则，继续往下。解出(x,y)，将k1=x反代回（*），得到X。于是X就是这两个方程的一个特解，通解就是 X‘=X+k*LCM(m1,m2)这个式子再一变形，得 X‘ mod LCM(m1,m2)=X这个方程一出来，说明我们实现了(1)(2)两个方程的合并。令 M=LCM(m1,m2)，R=r2-r1就可将合并后的方程记为 X mod M = R。然后，扩展到n个方程。用合并后的方程再来和其他的方程按这样的方式进行合并，最后就能只剩下一个方程 X mod M=R，其中 M=LCM(m1,m2,...,mn)。那么，X便是原模线性方程组的一个特解，通解为 X‘=X+k*M。如果，要得到X的最小正整数解，就还是原来那个方法：X%=M;if (X<0) X+=M;这么一来～～大功告成～～

#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>using namespace std;long long a,b,c,n,d;long long X,Y;void extend(long long A,long long B,long long &d,long long &x1,long long &y1){    if(B==0)//犯了一个低级失误如果写成long long d的话函数的值传回到主函数    {        x1=1;        y1=0;        d=A;        return ;    }    extend(B,A%B,d,x1,y1);    long long temp=x1;    x1=y1;    y1=temp-(A/B)*y1;    return ;}int main(){    long long a1,r1,a2,r2,i,j;    while(scanf("%lld",&n)!=EOF)    {        bool ifhave=true;        scanf("%lld%lld",&a1,&r1);        for(i=2; i<=n; i++)        {            scanf("%lld%lld",&a2,&r2);            a=a1;            b=a2;            c=r2-r1;            extend(a,b,d,X,Y);            if(c%d)            {                ifhave=false;                break;            }            long long t=b/d;            X=(X*(c/d)%t+t)%t;//最小解            r1=a1*X+r1;            a1=a1*(a2/d);        }        for(j=i+1; j<=n; j++)        {            scanf("%lld%lld",&a2,&r2);        }        if(!ifhave)        {            printf("-1\n");            continue;        }        printf("%lld\n",r1);    }    return  0;}