package solution;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class ChineaseRemainder {

    public static void main(String[] args) {
        List<BigInteger> n = new ArrayList<>();
        List<BigInteger> a = new ArrayList<>();
        List<BigInteger> b = new ArrayList<>();

        n.add(new BigInteger("12"));
        n.add(new BigInteger("5"));
        n.add(new BigInteger("11"));
        n.add(new BigInteger("19"));
        n.add(new BigInteger("29"));
        n.add(new BigInteger("17"));

        a.add(new BigInteger("19"));
        a.add(new BigInteger("13"));
        a.add(new BigInteger("31"));
        a.add(new BigInteger("53"));
        a.add(new BigInteger("97"));
        a.add(new BigInteger("123"));

        b.add(new BigInteger("11"));
        b.add(new BigInteger("29"));
        b.add(new BigInteger("34"));
        b.add(new BigInteger("47"));
        b.add(new BigInteger("101"));
        b.add(new BigInteger("131"));

//        BigInteger A = chineaseRemainder(a, n);
//        BigInteger B = chineaseRemainder(b, n);
        BigInteger A = new BigInteger("1");
        BigInteger B = new BigInteger("1");
        for(int i = 0; i < a.size(); i++) {
            A = A.multiply(a.get(i));
            B = B.multiply(b.get(i));
        }

        System.out.println("A = " + A);
        System.out.println("B = " + B);

        System.out.println("A + B = " + A.add(B));
        System.out.println("A * B = " + A.multiply(B));

        List<BigInteger> sum = new ArrayList<>();
        List<BigInteger> product = new ArrayList<>();

        for(int i = 0; i < a.size(); i++) {
            sum.add(a.get(i).add(b.get(i)));
            product.add(a.get(i).multiply(b.get(i)));
        }

        BigInteger addRes = chineaseRemainder(sum, n);
        BigInteger multiplyRes = chineaseRemainder(product, n);

        System.out.println("A + B = " + addRes);
        System.out.println("A * B = " + multiplyRes);
    }

    /**
     * Gets A which is mapped to a1, a2, ....., ak
     * @param a the mapping of A
     * @param lowerCaseNumbers the list m1, m2, m3 ....., mk
     * @return A which is mapped to a1, a2, ....., ak and satisfies the following
     * for every i = 1 to k : A = ai (mod mi)
     */
    static BigInteger chineaseRemainder(List<BigInteger> a, List<BigInteger> lowerCaseNumbers) {
        BigInteger sum = new BigInteger("0");

        // The product of all lower case numbers M = m1 * m2 * ....... * mk
        BigInteger capitalM = new BigInteger("1");
        for(int i = 0; i < lowerCaseNumbers.size(); i++) {
            capitalM = capitalM.multiply(lowerCaseNumbers.get(i));
        }

        ExtendedEuclids ex = new ExtendedEuclids();
        for(int i = 0; i < lowerCaseNumbers.size(); i++) {
            // Mi which is equal to M/mi
            BigInteger upperCaseNumber = capitalM.divide(lowerCaseNumbers.get(i));

            // The multiplicative inverse of Mi (mod mi)
            BigInteger mulInverse = ex.mulInverse(upperCaseNumber, lowerCaseNumbers.get(i));

            // The summation formula for the inverse mapping
            sum = sum.add(((a.get(i)).multiply(upperCaseNumber)).multiply(mulInverse));
        }
        return sum.mod(capitalM);
    }
}