#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>


using namespace std;

class PolynomF2 {
public:
	static std::vector<int> irr_coeffs;
	std::vector<int> coeffs;

	PolynomF2() {}
	PolynomF2(int n) {
		std::vector<int> tmp(n);
		coeffs = tmp;
	}
	PolynomF2(const std::vector<int>& p) {
		this->coeffs = p;
	}
	PolynomF2(const PolynomF2& p) :coeffs(p.coeffs) {}
	PolynomF2(std::string poly) {
		while (poly[poly.length() - 1] == '0')
			poly.erase(poly.length() - 1);
		std::vector<int> tmp(poly.length());
		for (int i = 0; i < poly.size(); i++) {
			tmp[poly.size() - i - 1] = (int)(poly[i] - '0');
		}
		coeffs = tmp;

	}


	void simplify() {
		std::vector<int> divider = irr_coeffs;
		std::vector<int> tmp = coeffs;
		while (tmp.size() >= divider.size()) {
			for (int i = 0; i < divider.size(); i++) {
				tmp[i] += divider[i];
				tmp[i] %= 2;
			}
			int index = 0;
			while (tmp[index] != 1)
				index++;
			tmp.erase(tmp.begin(), tmp.begin() + index);
		}
		coeffs = tmp;
	}




	void setIrrPolynom(std::string poly) {
		while (poly[poly.length() - 1] == '0')
			poly.erase(poly.length() - 1);

		std::vector<int> tmp(poly.length());

		for (int i = 0; i < poly.size(); i++) {
			tmp[poly.size() - i - 1] = (int)(poly[i] - '0');
		}
		irr_coeffs = tmp;
	}
	PolynomF2 operator+ (const PolynomF2& p) const {
		if (p.coeffs.size() == 0 && this->coeffs.size() == 0) {
			return PolynomF2();
		}
		int max = std::max(p.coeffs.size(), this->coeffs.size());
		int min = std::min(p.coeffs.size(), this->coeffs.size());
		std::vector<int> new_poly(max);
		for (int i = max - 1; i > max - min - 1; i--) {
			new_poly[i] = (this->coeffs[i] + p.coeffs[i]) % 2;
		}
		if (p.coeffs.size() == max) {
			for (int i = max - min - 1; i >= 0; i--) {
				new_poly[i] = p.coeffs[i];
			}
		}
		else {
			for (int i = max - min - 1; i >= 0; i--) {
				new_poly[i] = this->coeffs[i];
			}
		}
		PolynomF2 newp(new_poly);
		newp.simplify();
		return newp;
	}

	// first we multiply polynomials, than we find remainder in div by irreducible polynomial
	PolynomF2 operator*(const PolynomF2& p) const {

		int n = p.coeffs.size();
		int m = coeffs.size();
		std::vector<int> res(n + m);
		for (int i = 0; i < n + m; i++) {
			res[i] = 0;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				res[i + j] ^= p.coeffs[i] + coeffs[j];
			}
		}
		PolynomF2 resp(res);
		resp.simplify();
		return resp;

	}


	/*PolynomF2 operator/ (const PolynomF2& p) const {
	std::vector<int> divider = p.coeffs;
	std::vector<int> tmp = coeffs;
	std::vector<int> res(0);
	while (tmp.size() >= divider.size()) {
	for (int i = 0; i < divider.size(); i++) {
	tmp[i] += divider[i];
	tmp[i] %= 2;
	}
	res.push_back(1);
	int index = 0;
	while (tmp[index] != 1)
	index++;
	for (int i = 0; i < index; i++) {
	res.push_back(0);
	}
	tmp.erase(tmp.begin(), tmp.begin() + index);
	}
	return PolynomF2(tmp);
	}
	*/

	PolynomF2 operator% (const PolynomF2& p) const {
		std::vector<int> divider = p.coeffs;
		std::vector<int> tmp = coeffs;
		while (tmp.size() >= divider.size()) {
			for (int i = 0; i < divider.size(); i++) {
				tmp[i] += divider[i];
				tmp[i] %= 2;
			}
			int index = 0;
			while (tmp[index] != 1)
				index++;
			tmp.erase(tmp.begin(), tmp.begin() + index);
		}
		PolynomF2 res(tmp);
		res.simplify();
		return res;
	}

	PolynomF2 operator/ (const int k) const {

		PolynomF2 res(*this);
		PolynomF2 tmp(*this);


		for (int i = 1; i < k; i++) {
			res = res*tmp;
		}
		res.simplify();
		return res;
	}


	// find reverse element
	PolynomF2 reverseElement() const {
		int n = (int)(pow(2, coeffs.size() - 1)) - 2;
		PolynomF2 res(*this);
		PolynomF2 tmp(*this);


		for (int i = 1; i < n; i++) {
			res = res*tmp;
		}
		res.simplify();
		return res;
	}

	friend std::ostream& operator<<(std::ostream& os, const PolynomF2& p) {
		if (p.coeffs.size() == 0) {
			os << "0";
			return os;
		}
		os << "x^" << p.coeffs.size() - 1;

		for (int i = 2; i < p.coeffs.size() - 1; i++) {
			if (p.coeffs[i] == 1) {
				os << " + x^" << p.coeffs.size() - i;
			}
		}
		if (p.coeffs[p.coeffs.size() - 1] == 1) {
			os << " + 1";
		}

		return os;
	}

	friend std::istream& operator >> (std::istream& is, PolynomF2& p) {

		std::string str;
		cout << "Input polynom in binary representation" << endl;
		is >> str;

		PolynomF2 res(str);
		p = res;
		cout << p << endl;


		return is;
	}



};

int main() {


	std::string poly;
	std::string input1;
	std::string input2;
	PolynomF2 a;


	cout << "enter irreducable polynom" << endl;
	cin >> poly;
	a.setIrrPolynom(poly);
	cout << "enter polynom" << endl;
	cin >> a;
	PolynomF2 b(0);
	cout << "enter operation:(^,+,%,*)" << endl;
	char command;
	cin >> command;
	switch (command)
	{
	case '^':
		int k;
		cout << "Enter k:";
		cin >> k;
		cout << a / k;
		break;
	case '*':

		cin >> b;
		cout << a*b << endl;
		break;
	case '%':

		cin >> b;
		cout << a%b << endl;
		break;
	case '+':


		cin >> b;
		cout << a + b << endl;
		break;

	default:
		break;
	}

	return 0;
}