---

#include <iostream>
#include <stdexcept>

using namespace std;

class Fraction {
private:
    int A, B;

    static int nod(int x, int y) {
        if (x < 0) x = -x;
        if (y < 0) y = -y;

        while (y != 0) {
            int t = x % y;
            x = y;
            y = t;
        }
        return x == 0 ? 1 : x;
    }

    void normalize() {
        if (B == 0)
            throw invalid_argument("Знаменатель равен нулю");

        if (B < 0) {
            A = -A;
            B = -B;
        }

        int d = nod(A, B);
        A /= d;
        B /= d;
    }

public:
    Fraction() : A(0), B(1) {}

    Fraction(int a, int b) : A(a), B(b) {
        normalize();
    }

    void decompose(int& whole, Fraction& proper) const {
        whole = A / B;
        proper = Fraction(A % B, B);
    }

    Fraction operator+(const Fraction& other) const {
        return Fraction(A * other.B + other.A * B, B * other.B);
    }

    Fraction operator-(const Fraction& other) const {
        return Fraction(A * other.B - other.A * B, B * other.B);
    }

    Fraction operator*(const Fraction& other) const {
        return Fraction(A * other.A, B * other.B);
    }

    Fraction operator/(const Fraction& other) const {
        if (other.A == 0)
            throw invalid_argument("Деление на ноль");

        return Fraction(A * other.B, B * other.A);
    }

    Fraction& operator+=(const Fraction& other) {
        *this = *this + other;
        return *this;
    }

    Fraction& operator-=(const Fraction& other) {
        *this = *this - other;
        return *this;
    }

    Fraction& operator*=(const Fraction& other) {
        *this = *this * other;
        return *this;
    }

    Fraction& operator/=(const Fraction& other) {
        *this = *this / other;
        return *this;
    }

    friend ostream& operator<<(ostream& os, const Fraction& f) {
        os << f.A;
        if (f.B != 1)
            os << "/" << f.B;
        return os;
    }
};

class Polynomial {
private:
    int n;       // степень полинома
    double* a;   // a[i] — коэффициент при x^i

public:
    Polynomial() : n(0), a(new double[1]{0}) {}

    Polynomial(int degree, const double coefficients[]) {
        if (degree < 0)
            throw invalid_argument("Отрицательная степень");

        n = degree;
        a = new double[n + 1];

        for (int i = 0; i <= n; i++)
            a[i] = coefficients[i];

        update();
    }

    Polynomial(const Polynomial& other) {
        n = other.n;
        a = new double[n + 1];

        for (int i = 0; i <= n; i++)
            a[i] = other.a[i];
    }

    Polynomial(Polynomial&& other) {
        // Забираем массив, оставляя в other нулевой полином.
        double* empty = new double[1]{0};

        n = other.n;
        a = other.a;

        other.n = 0;
        other.a = empty;
    }

    ~Polynomial() {
        delete[] a;
    }

    Polynomial& operator=(const Polynomial& other) {
        if (this == &other)
            return *this;

        double* newA = new double[other.n + 1];

        for (int i = 0; i <= other.n; i++)
            newA[i] = other.a[i];

        delete[] a;
        a = newA;
        n = other.n;

        return *this;
    }

    Polynomial& operator=(Polynomial&& other) {
        if (this == &other)
            return *this;

        double* empty = new double[1]{0};

        delete[] a;
        n = other.n;
        a = other.a;

        other.n = 0;
        other.a = empty;

        return *this;
    }

    // Удаляет старшие члены с нулевыми коэффициентами.
    void update() {
        while (n > 0 && a[n] == 0)
            n--;
    }

    double operator()(double x) const {
        double result = 0;
        double power = 1;

        for (int i = 0; i <= n; i++) {
            result += a[i] * power;
            power *= x;
        }

        return result;
    }

    Polynomial& operator+=(const Polynomial& other) {
        int newN = n > other.n ? n : other.n;
        double* newA = new double[newN + 1];

        for (int i = 0; i <= newN; i++) {
            double first = i <= n ? a[i] : 0;
            double second = i <= other.n ? other.a[i] : 0;
            newA[i] = first + second;
        }

        delete[] a;
        a = newA;
        n = newN;
        update();

        return *this;
    }

    Polynomial& operator-=(const Polynomial& other) {
        int newN = n > other.n ? n : other.n;
        double* newA = new double[newN + 1];

        for (int i = 0; i <= newN; i++) {
            double first = i <= n ? a[i] : 0;
            double second = i <= other.n ? other.a[i] : 0;
            newA[i] = first - second;
        }

        delete[] a;
        a = newA;
        n = newN;
        update();

        return *this;
    }

    Polynomial& operator*=(const Polynomial& other) {
        int newN = n + other.n;
        double* newA = new double[newN + 1]{};

        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= other.n; j++)
                newA[i + j] += a[i] * other.a[j];

        delete[] a;
        a = newA;
        n = newN;
        update();

        return *this;
    }

    Polynomial operator+(const Polynomial& other) const {
        Polynomial result(*this);
        result += other;
        return result;
    }

    Polynomial operator-(const Polynomial& other) const {
        Polynomial result(*this);
        result -= other;
        return result;
    }

    Polynomial operator*(const Polynomial& other) const {
        Polynomial result(*this);
        result *= other;
        return result;
    }

    // this = quotient * divisor + remainder
    void divide(const Polynomial& divisor,
                Polynomial& quotient,
                Polynomial& remainder) const {
        if (divisor.n == 0 && divisor.a[0] == 0)
            throw invalid_argument("Деление на нулевой полином");

        Polynomial r(*this);
        Polynomial q;

        if (n >= divisor.n) {
            delete[] q.a;
            q.n = n - divisor.n;
            q.a = new double[q.n + 1]{};
        }

        while (r.n >= divisor.n && !(r.n == 0 && r.a[0] == 0)) {
            int power = r.n - divisor.n;
            double coefficient = r.a[r.n] / divisor.a[divisor.n];

            q.a[power] += coefficient;

            for (int i = 0; i <= divisor.n; i++)
                r.a[i + power] -= coefficient * divisor.a[i];

            // Старший член вычтен полностью.
            r.a[r.n] = 0;
            r.update();
        }

        q.update();
        quotient = q;
        remainder = r;
    }

    friend ostream& operator<<(ostream& os, const Polynomial& p) {
        for (int i = 0; i <= p.n; i++) {
            if (i > 0) os << " + ";
            os << p.a[i];

            if (i > 0) os << "*x";
            if (i > 1) os << "^" << i;
        }
        return os;
    }
};

int main() {
    Fraction f(7, 3);
    Fraction g(1, 6);

    cout << "f = " << f << endl;
    cout << "f + g = " << f + g << endl;
    cout << "f * g = " << f * g << endl;

    int whole;
    Fraction proper;
    f.decompose(whole, proper);
    cout << "7/3 = " << whole << " + " << proper << endl;

    double first[] = {1, 0, 1};   // 1 + x^2
    double second[] = {1, 1};     // 1 + x

    Polynomial p(2, first);
    Polynomial d(1, second);

    cout << "\np(x) = " << p << endl;
    cout << "d(x) = " << d << endl;
    cout << "p + d = " << p + d << endl;
    cout << "p * d = " << p * d << endl;
    cout << "p(2) = " << p(2) << endl;

    Polynomial quotient, remainder;
    p.divide(d, quotient, remainder);

    cout << "Частное: " << quotient << endl;   // -1 + x
    cout << "Остаток: " << remainder << endl;   // 2
}