(POJ) 2891. Strange Way to Express Integers [中國剩餘定理]

http://poj.org/problem?id=2891

進化(?) 版的中國剩餘定理

原題題意：給出k條 x === a (mod m)的式子，求出最小的答案。

因為這次的mod的數字不再是質數，就不能用公式解，所以要考慮一些其他的算法。

我們考慮解以下兩個聯立方程式，其中a1, m1, a2, m2 是已知的。

x1 === a1 (mod m1)
x2 === a2 (mid m2)

其中，我們可以把上面兩條式子改寫成

x1 - a1 = t1 * m1
x2 - a2 = t2 * m2

整理可得

a1 + t1 * m1 = a2 + t2 * m2

移項可得

t1 * m1 - t2 * m2 = a2 - a1

其中，m1, m2, a2, a1是已知的，上面那個式子就相當於求ax + by = c(其中a,b,c已知) 的一組合法整數解，就可以用extgcd(拓展歐基里德算法)來求解

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long LL;

LL extgcd(LL a,LL b,LL &x,LL &y)
{
    if (b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        LL d=extgcd(b,a%b,y,x);
        y -= (a/b)*x;
        return d;
    }
}

LL mull(LL a,LL b,LL mod)
{
    a %= mod;
    b %= mod;
    LL ret=0;
    LL now=a;
    while (b)
    {
        if (b&1)
        {
            ret += now;
            ret %= mod;
        }
        now += now;
        now %= mod;
        b >>= 1;
    }
    return ret;
}

int main ()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        vector<LL> a,m;
        for (int i=0;n>i;i++)
        {
            LL x,y;
            scanf("%lld %lld",&x,&y);
            a.push_back(y);
            m.push_back(x);
        }
        bool has_answer = true;
        LL nowa=0,nowm=0;
        for (int i=0;n>i;i++)
        {
            if (!i)
            {
                nowa = a[i];
                nowm = m[i];
                continue;
            }
            LL a1 = nowa, m1 = nowm;
            LL a2 = a[i], m2 = m[i];
            if (a1 > a2)
            {
                swap(a1,a2);
                swap(m1,m2);
            }
            LL t1,t2;
            LL gcd = extgcd(m1,m2,t1,t2);
            if ((a2-a1)%gcd != 0)
            {
                has_answer = false;
                break;
            }
            LL val = (a2-a1)/gcd;
            nowm = m1/gcd*m2;
            nowa = a1 + mull( mull(t1+nowm,val,nowm),m1,nowm );
            nowa %= nowm;
        }
        if (has_answer)
        {
            printf("%lld\n",nowa);
        }
        else
        {
            puts("-1");
        }
    }
}