Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- template<class T>
- class Polynomial {
- public:
- std::vector<T> a;
- public:
- Polynomial() {}
- Polynomial(const std::vector<T> &_a) : a(_a) { clear(); }
- Polynomial(const T &x) { a.resize(1); a[0] = x; clear(); }
- template<class It>
- Polynomial(It begin, It end) {
- while (begin != end) a.push_back(*begin++);
- clear();
- }
- bool operator==(const Polynomial &p) const { return a == p.a; }
- bool operator!=(const Polynomial &p) const { return a != p.a; }
- auto begin() const { return a.begin(); }
- auto end() const { return a.end(); }
- void clear() {
- while (!a.empty() && a.back() == T(0)) a.pop_back();
- }
- std::size_t size() const { return a.size(); }
- int Degree() const {
- return static_cast<int>(a.size()) - 1;
- }
- T operator[](std::size_t ind) const {
- return ind >= size() ? T(0) : a[ind];
- }
- T operator()(const T &x) const {
- T k = 1, ans = 0;
- for (const auto &i : a) {
- ans += k * i;
- k *= x;
- }
- return ans;
- }
- Polynomial& operator+=(const Polynomial &p) {
- for (std::size_t i = 0; i != p.size(); ++i) {
- if (i >= a.size()) a.push_back(0);
- a[i] += p[i];
- }
- clear();
- return *this;
- }
- Polynomial& operator-=(const Polynomial &p) {
- for (std::size_t i = 0; i != p.size(); ++i) {
- if (i >= a.size()) a.push_back(0);
- a[i] -= p[i];
- }
- clear();
- return *this;
- }
- friend Polynomial operator*(const Polynomial &a, const Polynomial &b) {
- Polynomial ans;
- ans.a.resize(a.size() + b.size());
- for (std::size_t i = 0; i != a.size(); ++i)
- for (std::size_t j = 0; j != b.size(); ++j)
- ans.a[i + j] += a[i] * b[j];
- ans.clear();
- return ans;
- }
- friend Polynomial operator&(const Polynomial &a, const Polynomial &b) {
- Polynomial ans, curr = T(1);
- for (auto i : a) {
- ans += curr * i;
- curr *= b;
- }
- ans.clear();
- return ans;
- }
- friend Polynomial operator+(Polynomial a, const Polynomial &b) {
- return a += b;
- }
- friend Polynomial operator-(Polynomial a, const Polynomial &b) {
- return a -= b;
- }
- Polynomial& operator*=(const Polynomial &p) {
- return *this = *this * p;
- }
- Polynomial addzero(int x) const {
- std::vector<T> newa;
- for (int i = 0; i < x; ++i) newa.push_back(T(0));
- for (auto i : a) newa.push_back(i);
- return Polynomial(newa);
- }
- friend Polynomial operator/(Polynomial f, Polynomial g) {
- Polynomial ans;
- while (f.Degree() >= g.Degree()) {
- T res = f.a.back() / g.a.back();
- int d = f.Degree() - g.Degree();
- ans += Polynomial(res).addzero(d);
- f -= g.addzero(d) * res;
- f.clear();
- }
- ans.clear();
- return ans;
- }
- friend Polynomial operator%(Polynomial f, Polynomial g) {
- return f - f / g * g;
- }
- friend Polynomial operator,(Polynomial a, Polynomial b) {
- return a == T(0) ? b : (b % a, a);
- }
- void printsign(std::ostream &str, T x, std::size_t i, bool flag = true) const {
- if (x < T(0)) str << "-", x = -x;
- else
- if (flag) str << "+";
- if (x != T(1) || i == 0) str << x;
- if (x != T(1) && i != 0) str << "*";
- if (i != 0) {
- str << "x";
- if (i != 1)
- str << "^" << i;
- }
- }
- friend std::ostream& operator<<(std::ostream &str, const Polynomial &p) {
- if (p.size() == 0) return str << T(0);
- for (int i = p.Degree(); ; --i) {
- if (p[i] != T(0))
- p.printsign(str, p[i], i, i != p.Degree());
- if (i == 0) break;
- }
- return str;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement