// -----------
// GCDLCM.java
// -----------

import java.math.BigInteger;

final class GCDLCM {
    /**
     * O(n) in space
     * O(n) in time
     * Precondition: (m >= 0) && (n >= 0)
     */
    public static long gcd (long m, long n) {
        assert (m >= 0) && (n >= 0);
        if (m == 0)
            return n;
        return gcd(n % m, m);}

    /**
     * O(n) in space
     * O(n) in time
     * Precondition: (m >= 0) && (n >= 0) && ((m > 0 || n > 0))
     */
    public static long lcm (long m, long n) {
        assert (m >= 0) && (n >= 0) && ((m > 0 || n > 0));
        return (m * n) / gcd(m, n);}}

final class GCDLCMTest {
    public static void main (String[] args) {
        System.out.println("GCDLCM.java");

        assert GCDLCM.gcd( 0,  0) ==   0;
        assert GCDLCM.gcd( 0,  1) ==   1;
        assert GCDLCM.gcd( 1,  0) ==   1;
        assert GCDLCM.gcd( 6,  9) ==   3;
        assert GCDLCM.gcd( 9,  6) ==   3;
        assert GCDLCM.gcd(21, 35) ==   7;
        assert GCDLCM.gcd(35, 21) ==   7;
        assert GCDLCM.gcd(22, 35) ==   1;

        assert new BigInteger("0").gcd(new BigInteger("0")).equals(new BigInteger("0"));
        assert new BigInteger("0").gcd(new BigInteger("1")).equals(new BigInteger("1"));
        assert new BigInteger("1").gcd(new BigInteger("0")).equals(new BigInteger("1"));
        assert new BigInteger("6").gcd(new BigInteger("9")).equals(new BigInteger("3"));
        assert new BigInteger("9").gcd(new BigInteger("6")).equals(new BigInteger("3"));
        assert new BigInteger("21").gcd(new BigInteger("35")).equals(new BigInteger("7"));
        assert new BigInteger("35").gcd(new BigInteger("21")).equals(new BigInteger("7"));
        assert new BigInteger("22").gcd(new BigInteger("35")).equals(new BigInteger("1"));

        assert GCDLCM.lcm( 0, 1)  ==   0;
        assert GCDLCM.lcm( 1, 0)  ==   0;
        assert GCDLCM.lcm( 6, 9)  ==  18;
        assert GCDLCM.lcm( 9, 6)  ==  18;
        assert GCDLCM.lcm(21, 35) == 105;
        assert GCDLCM.lcm(35, 21) == 105;
        assert GCDLCM.lcm(22, 35) == 770;

        System.out.println("Done.");}}