线性同余同余方程组解法(excrt)

2018-06-17 21:43:41来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

【问题描述】

求关于 x 的同余方程组

x%=1  a1=b1

x%=2  a2=b2

x%=3  a3=b3

x%=4  a4=b4

的大于等于 0 的最小整数解。

【输入格式】

一行 8 个整数,表示,,,,,,,4  a1,b1,a2,b2,a3,b3,a4,b4 。

【输出格式】

一行一个整数,答案除以 p 的余数。

【样例输入】

2 0 3 1 5 0 7 3

【样例输出】

10

【数据规模和约定】

对于 30% 的数据,i  ai ≤ 40, 保证 i  ai 均为素数。

对于 60% 的数据,110 3  1≤ai≤103 , 保证i  ai 均互素。

对于 100% 的数据,0<,110 3  0≤bi<ai,1≤ai≤103 。

【限制】

时间:1S

内存: 256M

 

/**********************一般模线性方程组***********************/

同样是求这个东西。。
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;

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 using namespace std;
 8 const int MAXN=100001;
 9 const int n=4;
10 inline void read(int &n)
11 {
12     char c=getchar();bool flag=0;n=0;
13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
15 }
16 int a[MAXN],b[MAXN];
17 int exgcd(int a,int b,int &x,int &y)
18 {
19     if(b==0)
20     {    x=1,y=0;return a;    }
21     int r=exgcd(b,a%b,x,y);
22     int tmp=x;x=y;y=tmp-(a/b)*y;
23     return r;
24 }
25 int x,y;
26 int gcd(int a,int b)
27 {
28     return b==0?a:gcd(b,a%b);
29 }
30 int lcm(int a,int b)
31 {
32     return a*b/(gcd(a,b));
33 }
34 inline int WORK()
35 {
36     /*
37         x+a1*y1=b1   1
38         x+a2*y2=b2   2
39         x+a3*y3=b3   3
40         求这个方程的解x 
41     */
42     int M=a[1],R=b[1],x,y;
43     // M=LCM(a1,a2)
44     // R=bi-b1
45     for(int i=2;i<=n;i++)
46     {
47         
48         /*
49         a1*y1-a2*y2=b2-b1
50         a*x  +b*y  =gcd(a,b)
51         这样求出y1之后
52         带回得到对于1,2两个方程的解x0=b1-y1*a1
53         */
54         int r=exgcd(M,a[i],x,y);
55         if( (R-b[i])%r!=0)    return -1;
56         /*   R-b[i]相当于b2-b1
57              方程有解的条件(b2-b1)%gcd(a,b) ==0 */
58         
59         x=(R-b[i])/r*x%a[i];//**** 
60         
61         
62         R=R-x*M;//x0=b1-y1*a1
63         M=M/r*a[i];// 新的模数 
64         R=R%M;//R=X mod M
65     }
66     return (R%M+M)%M;
67 }
68 int main()
69 {
70     
71     for(int i=1;i<=n;i++)
72         read(a[i]),read(b[i]);
73     printf("%d",WORK());
74     return 0;
75 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:POJ 27777 count color (线段树——带lazy标志)

下一篇:洛谷P2415 集合求和