polynomial gcd

#include<bits/stdc++.h>

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;

/*

INPUT FORMAT

p (you need to find gcd(a , b) in Zp)
n1 - degree of the first polynom
a_n1 ... a_0 - coefficients of a
n2 - degree of the second polynom
a_n2 ... a_0 - coefficients of b

EXAMPLE
You need to find gcd of 1x^3  +  -2x^2  +  1x^1  +  -2x^0
and 1x^4  +  -2x^3  +  0x^2  +  7x^1  +  -14x^0 in Zp

input:

2
3
1 -2 1 -2
4
1 -2 0 7 -14


*/




int mod = 2;


int modInverse(int a, int m){
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if(m == 1)
        return 0;

    while(a > 1){
        q = a / m;
        t = m;

        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    while(x1 < 0)
       x1 += m0;
    return x1;
}

struct polynom{
    int deg;
    vi a;
    polynom(){}

    polynom(int n , vi v){
        deg = n + 1;

        a = v;
    }

    polynom operator -(const polynom & other){
        polynom res;
        res.deg = max(deg , other.deg);
        vi v;
        rep(i , res.deg){
            int x = deg - i - 1;
            int y = other.deg - i - 1;
            int cur_x = x >= 0 ? a[x] : 0;
            int cur_y = y >= 0 ? other.a[y] : 0;
            v.pb(cur_x - cur_y);
        }
        while(sz(v) && v[sz(v) - 1] == 0)v.ppb();
        if(sz(v) == 0)v = {0};
        res.deg = sz(v);
        reverse(all(v));
        res.a  = v;
        return res;
    }

    polynom operator %(const polynom & other){
        polynom res;
        if(other.deg > deg)
            return *this;

        polynom tmp = *this;

        while(tmp.deg >= other.deg){
            int cur = tmp.deg - other.deg;
            int k = (tmp.a[0] * modInverse(other.a[0] , mod)) % mod;
            vi tmpa(tmp.deg);
            rep(i , tmp.deg){
                tmpa[i] = i < other.deg ? k * other.a[i] : 0;
            }
            polynom ct(tmp.deg - 1 , tmpa);
            tmp = tmp - ct;

        //  tmp.println();

            rep(i , tmp.a.size()){
                while(tmp.a[i] < 0)
                    tmp.a[i] += mod;
                tmp.a[i] %= mod;
            }

            reverse(all(tmp.a));
            while(sz(tmp.a) && tmp.a[sz(tmp.a) - 1] == 0){
                tmp.a.ppb();
            }
            if(sz(tmp.a) == 0)tmp.a = {0};
            tmp.deg = sz(tmp.a);
            reverse(all(tmp.a));
        }

        return tmp;
    }

    void field(){
        rep(i , sz(a)){
            while(a[i] < 0)
                a[i] += mod;
            a[i] %= mod;
        }
    }

    void println(){
        rep(i , deg){
            if(i != 0)
                cout << "  +  ";
            cout << a[i] << "x^" << deg - i - 1;
        }
        cout << nl;
    }
};

vector<pair<polynom , polynom>> st;



polynom gcd(polynom a , polynom b){
    a.field();
    b.field();
    st.pb({a , b});
    if(b.deg == 1){
        if(b.a[0] != 0){
            return polynom(0 , {1});
        }
        return a;
    }else{
        return gcd(b , a % b);
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(0);
    cin >> mod;
    int n1 , n2;
    cin >> n1;

    vi a(n1 + 1);

    rep(i , n1 + 1){
        cin >> a[i];
    }

    cin >> n2;

    vi b(n2 + 1);

    rep(i , n2 + 1){
        cin >> b[i];
    }


    polynom pa(n1 , a);
    polynom pb(n2 , b);

    cout << "Your input\n";
    cout << "a :  ";
    pa.println();

    cout << "b :  ";
    pb.println();
    cout << "Which equals to the following in Z" << mod << nl;

    pa.field();
    pb.field();

    cout << "a :  ";
    pa.println();

    cout << "b :  ";
    pb.println();


    auto m = gcd(pb , pa);

//  m.println();

    cout << "Euclid: \n";

    rep(i , sz(st)){
        cout << "Step " << i + 1 << nl;
        cout << "a :  ";
        st[i].fi.println();
        cout << "b :  ";
        st[i].se.println();
        cout << nl;
    }

    cout << "Thus, GCD(a , b) = ";
    m.println();

    return 0;
}