poj2891

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

这道题就是扩展的中国剩余定理（模数不互质）

首先我们回忆一下中国剩余定理对于给定n个方程组x≡ai(mod pi)

令m=∏pi wi=m/pi，然后求解关于hi,ri的方程wi*hi+pi*ri=1

令ei=wi*hi,则x≡∑eiai (mod m) 简单的验证一下，拿每个pi去模x，

因为除了wi意外，其他wj都是pi的倍数，很容易发现是复合条件的

但是当pi不互质时，上述就失效了，所以我们不能再用中国剩余定理

我们就觉得办法是用增量法，假设现在已经得到满足前k个同余方程的最小解ans

对于下一个方程x≡a(mod p),

我们不难想到满足单一同余方程的解x=a+p*k，满足前k个同余方程的解x=ans+lcm(pi)*k

现在我们只要令a+p*k=ans+lcm(pi)*k'，找到这个二元一次方程的解

就能找到满足前k+1个同余方程的最小解，显然这是用扩展欧几里得解决

注意这道题说输入和输出可以用int64表示，但很容易中间量爆int64，理论用高精度

实际全部用long long好像就能过了（注意discuss中部分数据会造成中间量爆int64，但可以忽视……）

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<stdlib.h>

 #define ll long long

 using namespace std;

 int k;

 ll a1,a2,p1,p2,x,y;

 ll gcd(ll a,ll b)

 {

    return (b==)?a:gcd(b,a%b);

 }

 void exgcd(ll a,ll b,ll &x,ll &y)

 {

      if (b==) {x=; y=; return;}

      exgcd(b,a%b,x,y);

      ll xx=x,yy=y;

      x=yy; y=xx-(a/b)*yy;

 }

 int main()

 {

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

     {

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

           a1%=p1;

           bool ch=;

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

           {

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

               if (ch) continue;

               a2%=p2;

               ll g=gcd(p1,p2);

               if ((a1-a2)%g)

               {

                  ch=;

                  continue;

               }

               ll a=p1/g,c=(a1-a2)/g;

               exgcd(a,p2/g,x,y); y=(y+a)%a;

               y=(y*c%a+a)%a;

               p1=p1*(p2/g); a1=(a2+p2*y%p1)%p1;

           }

           if (ch) puts("-1");

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

     }

     system("pause");

     return ;

 }