POJ 2891 Strange Way to Express Integers

POJ 2891 Strange Way to Express Integers | exGcd解同余方程组

题面就是让你解同余方程组(模数不互质)

题解:

先考虑一下两个方程

x=r1 mod(m1)

x=r2 mod (m2)

去掉mod

x=r1+m1y1 ......1

x=r2+m2y2 ......2

1-2可以得到

m1y1-m2y2=r1-r2

形同ax+by=c形式,可以判无解或者解出一个y1的值

带回1式可得到一个x的解x0=r1-y1a1

通解为x=x0+k*lcm(m1,m2)

即x=x0 mod(lcm(m1,m2))

令M=lcm(m1,m2) R=x0

所以x满足x=R mod(M)

就变成了一个新的式子

可以合并到最后啦

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define N 100010
 5 typedef long long ll;
 6 using namespace std;
 7 ll n,m[N],r[N];
 8 ll exGcd(ll a,ll b,ll &x,ll &y)
 9 {
10     if (b==0) return x=1,y=0,a;
11     ll r=exGcd(b,a%b,y,x);
12     y-=a/b*x;
13     return r;
14 }
15 ll solve()
16 {
17     ll M=m[1],R=r[1],x,y,d;
18     for (int i=2;i<=n;i++)
19     {
20     d=exGcd(M,m[i],x,y);
21     if ((R-r[i])%d!=0) return -1;
22     x=(R-r[i])/d*x%m[i];
23     R-=x*M;
24     M=M/d*m[i];
25     R%=M;
26     }
27     return (R%M+M)%M;
28 }
29 int main()
30 {
31     while (scanf("%lld",&n)!=EOF)
32     {
33     for (int i=1;i<=n;i++)
34         scanf("%lld%lld",&m[i],&r[i]);
35     printf("%lld
",solve());
36     }
37     return 0;
38 }