Chinese Remainder Theorem

Reading:
http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Here i make use of the following computational formula to calculate the solution of a system of simultaneous congruences using  Chinese Remainder Theorem:



Modular inverse is computed using Extended Euclid's Algorithm.

Implementation:

int egcd(int a, int b, LL &x, LL &y) {
    if(b == 0) {
        x = 1; y = 0; return a;
    }
    int gcd = egcd(b,a%b,y,x);
    y -= a/b*x;
    return gcd;
}

int crt(VI &a, VI &m) {
    int N=1,n=a.size();
    LL t,x,y,ret=0;
    REP(i,0,n) N *= m[i];
    REP(i,0,n) {
        t = N/m[i];
        egcd(t,m[i],x,y);
        ret = (ret + ((a[i]*t)%N)*x)%N;
    }
    if(ret < 0) ret += N;
    return ret;
}