Utility classes

class Math
{

    /**
     * Get the lowest common multiple of two numbers
     *
     * @param int $a
     * @param int $b
     * @return int
     */
    public static function lcm($a, $b)
    {
        return (int) gmp_lcm($a, $b);
    }

    /**
     * Get the biggest common divisor of two numbers
     *
     * @param int $a
     * @param int $b
     * @return int
     */
    public static function gcd($a, $b)
    {
        return (int) gmp_gcd($a, $b);
    }

    /**
     * Extended Greatest Common Divisor Algorithm
     * Returns:
     *  gcd: The greatest common divisor of a and b.
     *  x, y: Coefficients such that x*a + y*b = gcd
     */
    public static function egcd($a, $b) {
        if ($b == 0) return [$a, 1, 0];
        [$gcd, $x, $y] = static::egcd($b, $a % $b);
        return [$gcd, $y, $x - (int)($a / $b) * $y];
    }

    /**
     * Chinese remainder theorem
     *
     * @param array $offsets The remainders, or the offset where each cycle starts
     * @param array $cycles The moduli, or the length of each cycle
     * @return int The smallest number that satisfies all the congruences
     */
    public static function crt($remainders, $moduli) {
        $sum = 0;
        $prod = array_product($moduli);
        foreach ($moduli as $i => $modulus) {
            $p = intdiv($prod, $modulus);
            [$gcd, $x, $y] = Math::egcd($p, $modulus);
            if ($gcd != 1) return false;
            $sum += $remainders[$i] * $x * $p;
        }
        return Math::mod($sum, $prod);
    }

    /**
     * Modulo function that works with negative numbers
     *
     * @param int $a
     * @param int $b
     * @return int
     */
    public static function mod($a, $b)
    {
        return (int) gmp_mod($a, $b);
    }

    /**
     * Return the integer value of a division and its remainder
     *
     * @return [$quotient, $remainder]
     */
    public static function divmod($a, $b)
    {
        return [
            intdiv($a, $b),
            Math::mod($a, $b)
        ];
    }

    /**
     * Get all the divisors of a number
     *
     * @param int $n
     * @return array
     */
    public static function divisors($n)
    {
        $small_divisors = [];
        $large_divisors = [];

        for ($i = 1; $i <= sqrt($n); $i++) {
            if ($n % $i == 0) {
                $small_divisors[] = $i;
                if ($n != $i * $i) {
                    $large_divisors[] = $n / $i;
                }
            }
        }

        return array_merge($small_divisors, array_reverse($large_divisors));
    }

    /**
     * Sum of all numbers between two others (including)
     *
     * @param int $form
     * @param int $to
     * @return int
     */
    public static function seqSum($form, $to)
    {
        return ($to * ($to + 1) - $form * ($form - 1)) / 2;
    }

    /**
     * Quadratic equation
     * Finds x in ax^2 + bx + c = 0
     *
     * @param int $a
     * @param int $b
     * @param int $c
     * @param integer $sign
     * @return float|int
     */
    public static function quadratic($a, $b, $c, $sign = 1) {
        return (-$b + sqrt(($b*$b - (4*$a*$c))) * $sign) / (2*$a);
    }
}