POJ 2891 般模线性方程组

拼搏现实的明天。 2022-08-18 02:59 6阅读 0赞

题意：给出k个模方程组：x mod ai = ri。求x的最小正值。如果不存在这样的x，那么输出-1.

由于这道题目里面的ai、ri之间不满足两两互质的性质，所以不能用中国剩余定理直接求解。

X mod m1=r1  
X 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;

//poj 2891(一般模线性方程组)
    
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<queue>
    #include<map>
    #include<stack>
    #include<set>
    #include<cstdlib>
    
    using namespace std;
    
    #define LL long long
    const int inf = 0x3f3f3f3f;
    const int maxn = 1e5 + 5;
    int n;
    LL m[maxn], r[maxn];
    
    void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y)
    {
        if (!b) {d = a, x = 1, y = 0;}
        else
        {
            ex_gcd(b, a % b, d, y, x);
            y -= x * (a / b);
        }
    }
    
    LL ex_crt(LL *m, LL *r, int n)
    {
        LL M = m[1], R = r[1], x, y, d;
        for (int i = 2; i <= n; ++i)
        {
            ex_gcd(M, m[i], d, x, y);              //扩展欧几里得，d为M,m[i]的最大公约数
            if ((r[i] - R) % d) return -1;        //无解
            x = (r[i] - R) / d * x % (m[i] / d);   //满足条件的k的值
            R += x * M;                            //满足前i个条件的x
            M = M / d * m[i];                      //m的最小公倍数
            R %= M;
        }
        return R > 0 ? R : R + M ;
    }
    
    int main()
    {
        while (~scanf("%d",&n))
        {
            for (int i = 1; i <= n; ++i)
                scanf("%lld%lld", &m[i], & r[i]);
            printf("%lld\n",ex_crt(m,r,n));
        }
        return 0;
    }