【poj2891】同余方程组

同余方程组

例题1：pku2891Strange Way to Express Integers

中国剩余定理求的同余方程组mod 的数是两两互素的。然而本题（一般情况，也包括两两互素的情况，所以中国剩余定理成为了“时代的眼泪”）mod的数可能不是互素，所以要转换一下再求。

P=b1(mod a1); P / a1 ==?~~~~b1

P =b2(mod a2);

P =b3(mod a3);

……

P =bn(mod an);

a1~an,b1~bn是给出来的。

解：

第一条：a1*x+b1= P

第二条：a2*y+b2= P

第一条减去第二条： a1*x - a2*y = b2-b1

设A=a1,B=-a2,K=b2-b1，得到了x（实际调用exgcd的时候不理会a2前面的负号）

如果K%d!=0，无解

否则，X=[ (x* K/d)%(B/d)+(B/d) ]%(B/d)

LCU表示最小公倍数

P= a1*X+b1+ 若干倍的LCU(a1,a2)（或者把Y=(K-AX)/B，再P=a2*Y+b2+ 若干倍的LCU(a1,a2)

所以新的b= a1*x+b1，新的a= LCU(a1,a2)，

把新的b当成b1,新的a当成a1，再去和a3和b3结合，一直到最后结束，最后新的b就是X

 #include<cstdio>

 #include<cstring>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define LL long long

 LL a1,b1,a2,b2;

 LL ax,ay;

 LL exgcd(LL a,LL b)

 {

     if(b==) {ax=,ay=;return a;}

     LL g=exgcd(b,a%b);

     LL yy=ay;

     ay=ax-a/b*ay;ax=yy;

     return g;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     freopen("a.out","w",stdout);

     int n;

     while(scanf("%d",&n)!=EOF)

     {

         scanf("%lld%lld",&a1,&b1);

         bool ok=;

         for(int i=;i<=n;i++)

         {

             scanf("%lld%lld",&a2,&b2);

             if(!ok) continue;

             LL a,b,c,g;

             a=a1,b=a2,c=b2-b1;

             g=exgcd(a,b);

             if(c%g!=) {ok=;continue;}

             if(b/g<) b*=-;

             ax=((ax*c/g)%(b/g)+(b/g))%(b/g);

             a=b1+ax*a1;

             g=a1*a2/exgcd(a1,a2);

             a1=g;b1=a;

         }

         if(!ok) printf("-1\n");

         else printf("%lld\n",b1);

     }

     return ;

 }

【poj2891】

2016-02-02 09:44:06

秒客网

【poj2891】同余方程组

相关文章