#include <stdio.h>
#include <stdlib.h>

struct Polynomial {
    int deg;
    double* coeff;
};

struct Polynomial* addPolynomials(struct Polynomial* a, struct Polynomial* b) {
    int newDeg = a->deg > b->deg ? a->deg : b->deg;
    struct Polynomial* n = malloc(sizeof(*n));
    n->coeff = malloc((newDeg + 1) * sizeof(*n->coeff));

    for (int i = newDeg - abs(a->deg - b->deg); i >= 0; i--) {
         n->coeff[i] = a->coeff[i] + b->coeff[i];
    }

    if (a->deg > b->deg) {
        for (int i = a->deg; i > a->deg - abs(a->deg - b->deg); i--) {
            n->coeff[i] = a->coeff[i];
        }
    } else {
        for (int i = b->deg; i > b->deg - abs(a->deg - b->deg); i--) {
            n->coeff[i] = b->coeff[i];
        }
    }

    for (int i = newDeg; i >= 0; i--) {
        if (n->coeff[i] != 0.0) {
              n->deg = i;
              return n;
        }
    }
    n->deg = 0;
    return n;
}

struct Polynomial* substractPolynomials(struct Polynomial* a, struct Polynomial* b) {
    int newDeg = a->deg > b->deg ? a->deg : b->deg;
    struct Polynomial* n = malloc(sizeof(*n));
    n->coeff = malloc((newDeg + 1) * sizeof(*n->coeff));

    for (int i = newDeg - abs(a->deg - b->deg); i >= 0; i--) {
         n->coeff[i] = a->coeff[i] - b->coeff[i];
    }

    if (a->deg > b->deg) {
        for (int i = a->deg; i > a->deg - abs(a->deg - b->deg); i--) {
            n->coeff[i] = a->coeff[i];
        }
    } else {
        for (int i = b->deg; i > b->deg - abs(a->deg - b->deg); i--) {
            n->coeff[i] = -b->coeff[i];
        }
    }

    for (int i = newDeg; i >= 0; i--) {
        if (n->coeff[i] != 0.0) {
              n->deg = i;
              return n;
        }
    }
    n->deg = 0;
    return n;
}

struct Polynomial* multiplyPolynomials(struct Polynomial* a, struct Polynomial* b) {
    struct Polynomial* n = malloc(sizeof(*n));
    n->deg = a->deg + b->deg;
    n->coeff = calloc((a->deg + b->deg + 1), sizeof(*n->coeff));

    for (int i = 0; i < a->deg + 1; i++) {
        for (int j = 0; j < b->deg + 1; j++) {
            n->coeff[i + j] += a->coeff[i] * b->coeff[j];
        }
    }

    return n;
}

struct Polynomial* dividePolynomials(struct Polynomial* a, struct Polynomial* b, struct Polynomial* r) {
    if (a->deg < b->deg) return NULL;
    struct Polynomial* q = malloc(sizeof(*q));
    struct Polynomial* temp = malloc(sizeof(*temp));

    temp->coeff = malloc((a->deg + 1) * sizeof(*temp->coeff));
    temp->deg = a->deg;

    q->coeff = malloc((a->deg + 1) * sizeof(*q->coeff));
    q->deg = a->deg;

    for (int i = 0; i < a->deg + 1; i++) {
        temp->coeff[i] = a->coeff[i];
        q->coeff[i] = 0.0;
    }

    for (int i = a->deg - b->deg; i >= 0; i--) {
        q->coeff[i] = temp->coeff[b->deg + i] / b->coeff[b->deg];
        for (int j = b->deg + i - 1; j >= i; j--) {
            temp->coeff[j] -= q->coeff[i] * b->coeff[j - i];
        }
    }

    for (int i = 0; i < b->deg; i++) {
        r->coeff[i] = temp->coeff[i];
    }

    if (r->deg < a->deg) {
        for (int i = b->deg; i < r->deg + 1; i++) {
            r->coeff[i] = 0.0;
        }
    } else {
        for (int i = b->deg; i < a->deg + 1; i++) {
            r->coeff[i] = 0.0;
        }
    }

    free(temp->coeff);
    free(temp);

    findDeg(r);
    findDeg(q);

    return q;
}

struct Polynomial* GCD(struct Polynomial* a, struct Polynomial* b) {
    struct Polynomial* temp = malloc(sizeof(*temp));
    temp->deg = b->deg;
    temp->coeff = malloc((b->deg + 1) * sizeof(*temp->coeff));

    while (b->deg != 0) {
        temp->deg = b->deg;
        for (int i = 0; i < b->deg; i++) {
            temp->coeff[i] = b->coeff[i];
        }
        dividePolynomials(a, b, b);
        a->deg = temp->deg;
        for (int i = 0; i < temp->deg; i++) {
            a->coeff[i] = temp->coeff[i];
        }
        printf("%d\n", a->deg);
        printf("%d\n", b->deg);

    }

    findDeg(a);

    return a;
}

void printPolynomial(struct Polynomial* c) {
    if (c->deg == 0) return;
    for (int i = c->deg; i >= 0; i--) {
        if (c->coeff[i] < 0.0) {
            printf(" -%lfx^%d ", -c->coeff[i], i);
        } else if (c->coeff[i] > 0.0) {
            printf(" +%lfx^%d ", c->coeff[i], i);
        }
    }
}

void findDeg(struct Polynomial* p) {
    for (int i = p->deg; i >= 0; i--) {
        if (p->coeff[i] != 0.0) {
            p->deg = i;
            return;
        }
    }
    p->deg = 0;
}

int main(int argc, char** argv) {
    struct Polynomial* a = malloc(sizeof(*a));
    struct Polynomial* b = malloc(sizeof(*b));
    struct Polynomial* c = malloc(sizeof(*c));
    struct Polynomial* r = malloc(sizeof(*r));

    a->deg = 3;
    r->deg = a->deg;
    r->coeff = malloc((a->deg + 1) * sizeof(*r->coeff));
    a->coeff = malloc((a->deg + 1) * sizeof(*a->coeff));
    a->coeff[0] = -1;
    a->coeff[1] = -1;
    a->coeff[2] = 1;
    a->coeff[3] = 1;
    //a->coeff[4] = 1;




    b->deg = 2;
    b->coeff = malloc((b->deg + 1) * sizeof(*b->coeff));
    b->coeff[0] = -1;
    b->coeff[1] = 2;
    b->coeff[2] = 3;






    c = dividePolynomials(a, b, b);
    //c = dividePolynomials(a, b, b);

    //printf("\n%d\n", c->deg);

    printPolynomial(c);
    printf("\n");
    //printPolynomial(b);
    //for (int i = 0; i < b->deg; i++) printf("%lf", b->coeff[i]);
    printf("\n%d", c->deg);
    printf("\n%d", b->deg);
}