polynomial.lib

#pragma once

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>



template <typename T>
T fastpow(T a, T b) {
	if (!b)
		return 1;
	return b % 2 ? a * fastpow(a, b - 1) : fastpow(a * a, b / 2);
}



template <typename T>
struct polynomial {
	T exponentiation = NULL;
	std::vector <T> coefficient;

	T val(T x) {
		T value = 0;
		for (T i = 0; i <= exponentiation; ++i)
			value += coefficient[i] * fastpow(x, exponentiation - i);
		return value;
	}

	polynomial <T> operator+(polynomial <T> &b) {
		polynomial <T> x = *this, y = b, c;
		to_strange_view(x, y);
		for (T i = 0; i <= x.exponentiation; ++i)
			c.coefficient.push_back(x.coefficient[i] + y.coefficient[i]);
		c.to_normal_view();
		return c;
	}

	void operator+=(polynomial <T> &b) {
		polynomial <T> y = b;
		to_strange_view(*this, y);
		for (T i = 0; i <= this->exponentiation; ++i)
			this->coefficient[i] += y.coefficient[i];
		this->to_normal_view();
	}

	polynomial <T> operator-(polynomial <T> &b) {
		polynomial <T> x = *this, y = b, c;
		to_strange_view(x, y);
		for (T i = 0; i <= x.exponentiation; ++i)
			c.coefficient.push_back(x.coefficient[i] - y.coefficient[i]);
		c.to_normal_view();
		return c;
	}

	void operator-=(polynomial <T> &b) {
		polynomial <T> y = b;
		to_strange_view(*this, y);
		for (T i = 0; i <= this->exponentiation; ++i)
			this->coefficient[i] -= y.coefficient[i];
		this->to_normal_view();
	}

	polynomial <T> operator*(polynomial <T> &b) {
		polynomial <T> x = *this, y = b, c;
		to_strange_view(x, y);
		c.coefficient.resize(x.coefficient.size() + y.coefficient.size(), 0);
		for (size_t i = 0; i <= x.exponentiation; ++i) {
			for (size_t j = 0; j <= y.exponentiation; ++j)
				c.coefficient[i + j] += x.coefficient[i] * y.coefficient[j];
		}
		c.to_normal_view();
		return c;
	}

	void to_normal_view() {
		while (!(coefficient.empty() || coefficient[coefficient.size() - 1]))
			coefficient.pop_back();		
		if (!coefficient.size())
			coefficient.push_back(0);
		reverse(coefficient.begin(), coefficient.end());
		exponentiation = coefficient.size() - 1;
	}

	void print(std::string t) {
		if (t == "yes") {
			for (size_t i = 0; i <= exponentiation; ++i)
				std::cout << coefficient[i] << ' ';
			std::cout << '\n';
		}
		else {
			if (!exponentiation) {
				std::cout << coefficient[0] << '\n';
				return;
			}
			if (exponentiation == 1) {
				if (coefficient[0] != 1) {
					if (coefficient[0] != -1)
						std::cout << coefficient[0];
					else
						std::cout << '-';
				}
				std::cout << 'x';
				if (coefficient[1]) {
					if (coefficient[1] > 0)
						std::cout << '+';
					std::cout << coefficient[1];
				}
				std::cout << '\n';
				return;
			}
			if (coefficient[0] != 1) {
				if (coefficient[0] != -1)
					std::cout << coefficient[0];
				else
					std::cout << '-';
			}
			std::cout << "x^" << exponentiation;
			for (T i = 1; i <= exponentiation - 2; ++i) {
				if (coefficient[i]) {
					if (coefficient[i] > 0)
						std::cout << '+';
					if (coefficient[i] == -1)
						std::cout << '-';
					else {
						if (coefficient[i] != 1)
							std::cout << coefficient[i];
					}
					std::cout << "x^" << exponentiation - i;
				}
			}
			if (coefficient[exponentiation - 1]) {
				if (coefficient[exponentiation - 1] > 0)
					std::cout << '+';
				if (coefficient[exponentiation - 1] == -1)
					std::cout << '-';
				else {
					if (coefficient[exponentiation - 1] != 1)
						std::cout << coefficient[exponentiation - 1];
				}
				std::cout << 'x';
			}
			if (coefficient[exponentiation]) {
				if (coefficient[exponentiation] > 0)
					std::cout << '+';
				std::cout << coefficient[exponentiation];
			}
			std::cout << '\n';
		}
	}
};


template <typename T>
std::istream& operator>> (std::istream& in, polynomial <T> &pol) {
	using namespace std;
	string _str;
	getline(cin, _str);
	vector<char> str;
	for (int i = 0; i < _str.size(); i++) {
		if (_str[i] != ' ') {
			str.push_back(_str[i]);
		}
	}
	int cod = 0, pos = 0, num = 0, numc = 0;
	bool sign = 0;;
	while (pos < str.size()) {
		if (str[pos] >= '0' && str[pos] <= '9') {
			num = num * 10 + (str[pos] - '0');
			pos++;
		}
		else if ((str[pos] >= 'a' && str[pos] <= 'z') || (str[pos] >= 'A' && str[pos] <= 'Z')) {
			if (sign) {
				num = -num;
			}
			pos++;
			long long num1 = 1;
			if (pos < str.size() && str[pos] == '^') {
				pos++;
				num1 = 0;
				while (str[pos] >= '0' && str[pos] <= '9') {
					num1 = num1 * 10 + (str[pos] - '0');
					pos++;
				}
			}
			if (pol.exponentiation == NULL) {
				pol.exponentiation = num1;
				pol.coefficient.resize(num1 + 1);
			}
			for (numc; numc < pol.exponentiation - num1; numc++) {
				pol.coefficient[numc] = 0;
			}
			if (num == 0) {
				pol.coefficient[numc] = 1;
			}
			else {
				pol.coefficient[numc] = num;
			}
			num = 0;
			numc++;
		}
		else if (str[pos] == '-') {
			sign = 1;
			pos++;
		}
		else if (str[pos] == '+') {
			sign = 0;
			pos++;
		}
	}
	if (sign) {
		num = -num;
	}
	for (numc; numc < pol.exponentiation; numc++) {
		pol.coefficient[numc] = 0;
	}
	pol.coefficient[numc] = num;
	return in;
}

template <typename T>
void to_strange_view(polynomial <T> &a, polynomial <T> &b) {
	reverse(a.coefficient.begin(), a.coefficient.end());
	reverse(b.coefficient.begin(), b.coefficient.end());
	while (a.coefficient.size() < b.coefficient.size())
		a.coefficient.push_back(0);
	while (b.coefficient.size() < a.coefficient.size())
		b.coefficient.push_back(0);
	a.exponentiation = a.coefficient.size() - 1;
	b.exponentiation = b.coefficient.size() - 1;
}


template <typename T>
polynomial <T> pw(polynomial <T> a, T k) {
	if (!k)
		return { 0, { 1 } };
	return k % 2 ? a * pw(a, k - 1) : pw(a * a, k / 2);
}

template <typename T>
polynomial <T> gcd(polynomial <T> &a, polynomial <T> &b) { // doesn't work now
	while (a.exponentiation && b.exponentiation) {
		if (a.exponentiation > b.exponentiation)
			a -= b;
		else
			b -= a;
	}
	return a + b;	
}