garner.java

class Lib{
    /* Verify
       http://codeforces.com/contest/903/submission/33247715
       http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2647639
    */
    /* 参考 http://math314.hateblo.jp/entry/2015/05/07/014908 */
    static long extgcd(long a,long b,long[]x) {
        for (long u = x[1] = 1, v = x[0] = 0; a!=0;){
            long q = b / a;
            long r=x[0]-q*u;
            x[0]=u;
            u=r;
            r=x[1]-q*v;
            x[1]=v;
            v=r;
            r=b-q*a;
            b=a;
            a=r;
        }
        return b;
    }

    static long mod_inv(long a,long m) {
        long[]x=new long[2];
        extgcd(a, m, x);
        return (m + x[0] % m) % m;
    }
    /*
      x==a[i] (mod m[i])を満たすxのうち、絶対値最小のものを返す。
      事前条件 a.length==m.length
      計算量 O(a.length^2)
    */
    public static BigInteger garner(long[]a,long[]m){
        int ms=a.length;
        long[]coffs=new long[ms],constants=new long[ms];
        long[]digs=new long[ms];
        Arrays.fill(coffs,1);
        for(int i=0;i<ms;++i){
            long v = (a[i] - constants[i]) * mod_inv(coffs[i], m[i]) % m[i];
            if(v<0)v+=m[i];
            digs[i]=v;
            for (int j = i + 1; j < ms; j++) {
                constants[j] += coffs[j] * v;
                constants[j] %= m[j];
                coffs[j] *= m[i];
                coffs[j] %= m[j];
            }
        }
        BigInteger ans=BigInteger.valueOf(0),c=BigInteger.valueOf(1);
        for(int i=ms-1;i>=0;--i){
            c=c.multiply(BigInteger.valueOf(m[i]));
            ans=ans.multiply(BigInteger.valueOf(m[i]));
            ans=ans.add(BigInteger.valueOf(digs[i]));
        }
        if(ans.compareTo(c.divide(BigInteger.valueOf(2)))>0)
            ans=ans.subtract(c);
        return ans;
    }
}