POJ 2891- Strange Way to Express Integers CRT 除数非互质

**题意：**给你余数和除数求x 注意除数不一定互质
**思路:**不互质的CRT需要的是将两个余数方程合并，需要用到扩展GCD的性质

合并互质求余方程

m1x -+ m2y = r2 - r1 先用exgcd求出特解x0, y0(m1x + m2y = g)

等式两边都乘以c/g 那么可以得解为 x1 = cx0/g，y1 = cy0/g

由性质可知 通解x' = x1 + km2/g，y' = y1 + km1/g 其中k为任意整数

即 x' = cx0/g + km2/g

设 t = m2/g

为保证x是正数 可以将式子化成 x' = (cx0/d % t + t)%t 因为必定存在k使 cx0/g + kt = ( (cx0/g)%t + t)%t

最后合并的取余式为 X = (m1 * x' + r1) (mod lcm(m1, m2) )

#include <stdio.h>


#include <iostream>


#include <string.h>


#include <algorithm>


#include <utility>


#include <vector>


#include <map>


#include <set>


#include <string>


#include <stack>


#include <queue>


#define LL long long


#define ll __int64


#define MMF(x) memset((x),0,sizeof(x))


#define MMI(x) memset((x), INF, sizeof(x))


using namespace std;





const int INF = 0x3f3f3f3f;


const int N = 1e5+2000;





ll gcd(ll a, ll b)


{


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


}





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


{


    ll d = a;


    if(!b)


    {


        x = 1;


        y = 0;


    }


    else


    {


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


        y -= (a / b) * x;


    }


    return d;


}








int main()


{


    ll n;


    while(~scanf("%I64d", &n))


    {


        ll x, y;


        ll m, r;


        ll mt, rt;


        int flag = 0;


        scanf("%I64d%I64d", &m, &r);


        for(int i = 0; i < n - 1; i++)


        {


            scanf("%I64d%I64d", &mt, &rt);


            ll c = rt - r;


            ll g = gcd(m, mt);


            if(c % g!=0)


            {


                flag = 1;


            }


            else


            {


                exgcd(m, mt, x, y);


                ll t = mt / g;


                x = (c / g * x % t + t) % t;


                r = m * x + r;


                m = m /gcd(m, mt) * mt;


            }


        }


        if(flag == 1)


            printf("-1\n");


        else printf("%I64d\n", r);


    }


    return 0;


}