本文主要是介绍POJ 2891 模线性方程组（mi mj 不互素)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题解：
x = ai ( mod mi ) 1 <= i <= k
先考虑k==2的情况：
x = a1 ( mod m1 )
x = a2 ( mod m2 )
方程组有解的充分必要条件是： d | (a1-a2) ，其中 d = (m1,m2)
证明如下：
必要性： 设 x 是上面同余方程组的解，从而存在整数q1,q2使得x=a1+m1*q1，x=a2+m2*q2，消去x即得a1-a2 = m2q2-m1q1。由于d=(m1,m2)，故d | (a1-a2)。
充分性：若d=(m1,m2) | (a1-a2)成立，则方程m1*x + m2*y = a1-a2有解。
设解为x0,y0。那么m2*y0 = a1-a2 ( mod m1 )
记x1 = a2+m2*y0，可以知道 x1=a2 ( mod m2 )，且x1 = a2+m2*y0 = a2 + ( a1-a2) = a1 ( mod m1 )
所以 x1 = a2 ( mod m2 ) = a1 ( mod m1 )
所以 x = x1 ( mod [m1,m2] )
另外，若x1与x2都是上面同余方程组的解，则 x1 = x2 ( mod m1 )， x1 = x2 ( mod m2 )， 由同余的性质得 x1 = x2 ( mod [m1,m2] )，即对于模[m1,m2]，同余方程组的解释唯一的。
证毕。
····
k>2的情形。略。
#include<cstdio>
#define lint __int64lint Egcd ( lint a, lint b, lint &x, lint &y )
{lint tmp, ret;if ( b == 0 ){x = 1, y = 0;return a;}ret = Egcd ( b, a % b, x, y );tmp = x, x = y, y = tmp-a/b*y;return ret;
}lint gcd ( lint a, lint b )
{if ( b == 0 )return a;return gcd ( b, a % b );
}//求模线性方程组 ax = b ( mod m )
lint modular_linear ( lint a, lint b, lint m )
{lint d, x, y;d = Egcd ( a, m, x, y );if ( b % d != 0 ) return -1; // 无解则返回-1。return ( x * (b/d) % m + m ) % m;
}int main()
{lint a1, a2, m1, m2, k, y;while ( scanf("%I64d",&k) != EOF ){bool flag = false;scanf("%I64d%I64d",&m1,&a1);if ( k == 1 ) y = a1;for ( int i = 1; i < k; i++ ){scanf("%I64d%I64d",&m2,&a2);if ( flag ) continue;lint y = modular_linear ( m2, a1 - a2, m1 );if ( y == -1 ) { flag = true; continue; }a1 = a2 + m2 * y;m1 = m1*m2/gcd(m1,m2);a1 = ( a1 % m1 + m1 ) % m1;}if ( flag ) printf("-1\n");else printf("%I64d\n",a1);}return 0;
}
这篇关于POJ 2891 模线性方程组（mi mj 不互素)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
