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

【问题描述】

求关于 x 的同余方程组

x%a 1 =b 1  a1=b1

x%a 2 =b 2  a2=b2

x%a 3 =b 3  a3=b3

x%a 4 =b 4  a4=b4

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

【输入格式】

一行 8 个整数,表示a 1 ,b 1 ,a 2 ,b 2 ,a 3 ,b 3 ,a 4 ,b 4  a1,b1,a2,b2,a3,b3,a4,b4 。

【输出格式】

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

【样例输入】

2 0 3 1 5 0 7 3

【样例输出】

10

【数据规模和约定】

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

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

对于 100% 的数据,0≤b i <a i ,1≤a i ≤10 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数值分析与有限元编程

有限元 | 二次样条梁单元

样条梁单元是样条函数与有限元法相结合的产物。有限元法将结构分割成若干单元,位移场采用分段插值或者分区插值。常用的插值方法有Lagrange插值,Hermite插...

3828
来自专栏mwangblog

用遗传算法求函数最大值一:编码和适应值

求函数 f(x)=9×sin(5x)+8×cos(4x), x∈[5,10] 的最大值。

1802
来自专栏行者常至

pgsql GIS 将线段等分,均分,为点 st_lineinterpolatepoint

geometry ST_LineInterpolatePoint(geometry a_linestring, float8 a_fraction);

1252
来自专栏蜉蝣禅修之道

Levenshtein distance最小编辑距离算法实现

6074
来自专栏数据结构与算法

P3389 【模板】高斯消元法

题目背景 Gauss消元 题目描述 给定一个线性方程组,对其求解 输入输出格式 输入格式: 第一行,一个正整数 nn 第二至 n+1n+1行,每行 n+1n+1...

3759
来自专栏书山有路勤为径

Face Generation

部署 model_opt 函数实现对 GANs 的优化。使用 tf.trainable_variables 获取可训练的所有变量。通过变量空间名 discrim...

802
来自专栏数据结构与算法

T4701 【卜卜】树状数组模板

题目描述 在二维平面内给定n个点: 0 x y v表示给(x,y)的权值减去v 1 x y v表示给(x,y)的权值加上v 然后有m个操作 0 x y v ,...

2887
来自专栏专注研发

poj-1005-l tanink i need a houseboat

Fred Mapper is considering purchasing some land in Louisiana to build his house ...

822
来自专栏小樱的经验随笔

容斥原理

容斥原理 对容斥原理的描述 容斥原理是一种重要的组合数学方法,可以让你求解任意大小的集合,或者计算复合事件的概率。 描述 容斥原理可以描述如下: 要计算几个...

4197
来自专栏机器学习和数学

[编程经验] Tensorflow中的共享变量机制小结

今天说一下tensorflow的变量共享机制,首先为什么会有变量共享机制? 这个还是要扯一下生成对抗网络GAN,我们知道GAN由两个网络组成,一个是生成器网络G...

7893

扫码关注云+社区