nod_polynoms

#include <iostream>
#include <vector>
typedef long long i64;
using namespace std;

int deconv(vector < i64 > &a, vector < i64 > &b, vector < i64 > &q, vector < i64 > &r, i64 n);
vector<i64> nod (vector<i64> a, vector<i64> b, i64 n);
void to_ring(i64 & x, i64 n);
void printv(vector < i64 > &v);

int main()
{
        vector < i64 > a{1,0,0,0,1,1,1,1,1};
        vector < i64 > b{1,0,1,0,1,1,0,1};
        vector < i64 > q, r;
        auto answer = nod(a, b, 2);
        printv(a);
        printv(b);
        printv(answer);
}

vector<i64> nod (vector<i64> a, vector<i64> b, i64 n){
//находит НОД двух многочленов в кольце вычетов по модулю n
//чтобы выключить дополнение с кольцом вычетов нужно передать ноль вместо n
        vector<i64> q, r;
        deconv(a, b, q, r, n);
        do {
                a = b;
                b = r;
                deconv (a, b, q, r, n);
        } while (r.front() != 0);
        return b;
}

void to_ring(i64 & x, i64 n){
//загоняет х в диапазон 0..n-1
        if ( n != 0 ){
        while (x>n) x -= n;
        while (x<0) x+= n;
        }
}

int deconv(vector < i64 > &a, vector < i64 > &b, vector < i64 > &q, vector < i64 > &r, i64 n)
// делит многочлен на многочлен
{
        q.clear();
        r = a;
        i64 limit = r.size() - b.size() + 1;
        for (i64 j = 0; j < limit; ++j)
        {
                q.push_back(r[j] / b.front());
                to_ring(q.back(), n);
                for (i64 i = 0; i < b.size(); ++i){
                        r[i + j] -= q.back() * b[i];
                        to_ring(r[i+j], n);
                }
        }
        i64 i;
        for (i=0; (i<r.size()-1) &&( r[i] == 0);++i);
        r.erase (r.begin(), r.begin()+i);
        return 0;
}

void printv(vector < i64 > &v)
//выводит вектор на экран
{
  for (auto & i:v)
        cout << i << " ";
    cout << endl;
}