数论六·模线性方程组

#1303 : 数论六·模线性方程组

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Ho：今天我听到一个挺有意思的故事！

小Hi：什么故事啊？

小Ho：说秦末，刘邦的将军韩信带领1500名士兵经历了一场战斗，战死四百余人。韩信为了清点人数让士兵站成三人一排，多出来两人；站成五人一排，多出来四人；站成七人一排，多出来六人。韩信立刻就知道了剩余人数为1049人。

小Hi：韩信点兵嘛，这个故事很有名的。

小Ho：我觉得这里面一定有什么巧妙的计算方法！不然韩信不可能这么快计算出来。

小Hi：那我们不妨将这个故事的数学模型提取出来看看？

小Ho：好！

<小Ho稍微思考了一下>

小Ho：韩信是为了计算的是士兵的人数，那么我们设这个人数为x。三人成排，五人成排，七人成排，即x mod 3, x mod 5, x mod 7。也就是说我们可以列出一组方程：

x mod 3 = 2
x mod 5 = 4
x mod 7 = 6

韩信就是根据这个方程组，解出了x的值。

小Hi：嗯，就是这样！我们将这个方程组推广到一般形式：给定了n组除数m[i]和余数r[i]，通过这n组(m[i],r[i])求解一个x，使得x mod m[i] = r[i]。

小Ho：我怎么感觉这个方程组有固定的解法？

小Hi：这个方程组被称为模线性方程组。它确实有固定的解决方法。不过在我告诉你解法之前，你不如先自己想想怎么求解如何？

小Ho：好啊，让我先试试啊！

输入

第1行：1个正整数, N，2≤N≤1,000。

第2..N+1行：2个正整数, 第i+1行表示第i组m,r，2≤m≤20,000,000，0≤r<m。

计算过程中尽量使用64位整型。

输出

第1行：1个整数，表示满足要求的最小X，若无解输出-1。答案范围在64位整型内。

样例输入

样例输出

不能直接套用中国剩余定理，因为能用中国剩余定理的条件是模数都是互质的。

所以要合并不互质的方程。

考虑这两个方程：

x=m1*k1+r1,
x=m2*k2+r2.

m1*k1+r1=m2*k2+r2.

m1*k1-m2*k2=r2-r1.

因为m1,m2,r1,r2都是已知的,所以可以用exgcd
求出k1和k2。

若无解，则原方程组也是无解的。

求出k1后，代入方程①，求出ｘ。

把ｘ看成一个特解，然后扩展出解系：

Ｘ＝x+k*lcm(m1,m2);在这里顺便求出了最小公倍数。

令Ｍ＝lcm(m1,m2),Ｒ＝x。

原方程转化为X=R+k*M。

这样就把上面两个同余方程合并成了一个同余方程，这样一直合并下去，最终会只剩一个方程，所以最终的Ｒ就是答案。

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<string>
 8 #include<vector>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 #define maxn 10100
15 #define LL long long 
16 using namespace std;
17 LL b[maxn],w[maxn],sum=1;
18 void exgcd(LL a,LL b,LL &x,LL &y){
19   if(b==0) x=1,y=0;
20   else exgcd(b,(a+b)%b,y,x),y-=x*(a/b);
21 }
22 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
23 int main()
24 {
25   freopen("!.in","r",stdin);
26   freopen("!.out","w",stdout);
27   int n;
28   scanf("%d",&n);
29   for(int i=1;i<=n;i++)
30     scanf("%lld%lld",&w[i],&b[i]);
31   /*for(int i=1;i<=n;i++){
32     LL m=sum/w[i];
33     LL x,y;
34     if(gcd(w[i],m)!=1) printf("-1"),exit(0);
35     exgcd(w[i],m,x,y);
36     while(y<0) y+=w[i];
37     ans+=y*m*b[i];
38     ans%=sum;
39     }*///直接用中国剩余定理会ＷＡ，因为要模数都互质才能用。
40   LL M=w[1],R=b[1],d,k1,k2,c;  
41   for(int i=2; i<=n; i++)  
42     {
43       d=gcd(M,w[i]);
44       c=b[i]-R;
45       if(c%d) printf("-1"),exit(0);
46       exgcd(M/d,w[i]/d,k1,k2);
47       k1=(c/d*k1)%(w[i]/d);
48       R+=M*k1;
49       M=M/d*w[i];
50       R%=M;
51     }
52   while(R<0) R+=M;
53   printf("%lld",R);
54   return 0;
55 }