SHARE
TWEET

Untitled

a guest Oct 13th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. template<class T>
  5. class Polynomial {
  6. public:
  7.     std::vector<T> a;
  8.  
  9. public:
  10.     Polynomial() {}
  11.     Polynomial(const std::vector<T> &_a) : a(_a) { clear(); }
  12.     Polynomial(const T &x) { a.resize(1); a[0] = x; clear(); }
  13.     template<class It>
  14.     Polynomial(It begin, It end) {
  15.         while (begin != end) a.push_back(*begin++);
  16.         clear();
  17.     }
  18.     bool operator==(const Polynomial &p) const { return a == p.a; }
  19.     bool operator!=(const Polynomial &p) const { return a != p.a; }
  20.  
  21.     auto begin() const { return a.begin(); }
  22.     auto end() const { return a.end(); }
  23.  
  24.     void clear() {
  25.         while (!a.empty() && a.back() == T(0)) a.pop_back();
  26.     }
  27.     std::size_t size() const { return a.size(); }
  28.  
  29.     int Degree() const {
  30.         return static_cast<int>(a.size()) - 1;
  31.     }
  32.  
  33.     T operator[](std::size_t ind) const {
  34.         return ind >= size() ? T(0) : a[ind];
  35.     }
  36.  
  37.     T operator()(const T &x) const {
  38.         T k = 1, ans = 0;
  39.         for (const auto &i : a) {
  40.             ans += k * i;
  41.             k *= x;
  42.         }
  43.         return ans;
  44.     }
  45.  
  46.     Polynomial& operator+=(const Polynomial &p) {
  47.         for (std::size_t i = 0; i != p.size(); ++i) {
  48.             if (i >= a.size()) a.push_back(0);
  49.             a[i] += p[i];
  50.         }
  51.         clear();
  52.         return *this;
  53.     }
  54.  
  55.     Polynomial& operator-=(const Polynomial &p) {
  56.         for (std::size_t i = 0; i != p.size(); ++i) {
  57.             if (i >= a.size()) a.push_back(0);
  58.             a[i] -= p[i];
  59.         }
  60.         clear();
  61.         return *this;
  62.     }
  63.     friend Polynomial operator*(const Polynomial &a, const Polynomial &b) {
  64.         Polynomial ans;
  65.         ans.a.resize(a.size() + b.size());
  66.         for (std::size_t i = 0; i != a.size(); ++i)
  67.             for (std::size_t j = 0; j != b.size(); ++j)
  68.                 ans.a[i + j] += a[i] * b[j];
  69.         ans.clear();
  70.         return ans;
  71.     }
  72.  
  73.     friend Polynomial operator&(const Polynomial &a, const Polynomial &b) {
  74.         Polynomial ans, curr = T(1);
  75.         for (auto i : a) {
  76.             ans += curr * i;
  77.             curr *= b;
  78.         }
  79.         ans.clear();
  80.         return ans;
  81.     }
  82.  
  83.     friend Polynomial operator+(Polynomial a, const Polynomial &b) {
  84.         return a += b;
  85.     }
  86.  
  87.     friend Polynomial operator-(Polynomial a, const Polynomial &b) {
  88.         return a -= b;
  89.     }
  90.  
  91.     Polynomial& operator*=(const Polynomial &p) {
  92.         return *this = *this * p;
  93.     }
  94.  
  95.     Polynomial addzero(int x) const {
  96.         std::vector<T> newa;
  97.         for (int i = 0; i < x; ++i) newa.push_back(T(0));
  98.         for (auto i : a) newa.push_back(i);
  99.         return Polynomial(newa);
  100.     }
  101.  
  102.     friend Polynomial operator/(Polynomial f, Polynomial g) {
  103.         Polynomial ans;
  104.         while (f.Degree() >= g.Degree()) {
  105.             T res = f.a.back() / g.a.back();
  106.             int d = f.Degree() - g.Degree();
  107.             ans += Polynomial(res).addzero(d);
  108.             f -= g.addzero(d) * res;
  109.             f.clear();
  110.         }
  111.         ans.clear();
  112.         return ans;
  113.     }
  114.  
  115.     friend Polynomial operator%(Polynomial f, Polynomial g) {
  116.         return f - f / g * g;
  117.     }
  118.  
  119.     friend Polynomial operator,(Polynomial a, Polynomial b) {
  120.         return a == T(0) ? b : (b % a, a);
  121.     }
  122.  
  123.     void printsign(std::ostream &str, T x, std::size_t i, bool flag = true) const {
  124.         if (x < T(0)) str << "-", x = -x;
  125.         else
  126.             if (flag) str << "+";
  127.         if (x != T(1) || i == 0) str << x;
  128.         if (x != T(1) && i != 0) str << "*";
  129.         if (i != 0) {
  130.             str << "x";
  131.             if (i != 1)
  132.                 str << "^" << i;
  133.         }
  134.     }
  135.  
  136.     friend std::ostream& operator<<(std::ostream &str, const Polynomial &p) {
  137.         if (p.size() == 0) return str << T(0);
  138.         for (int i = p.Degree(); ; --i) {
  139.             if (p[i] != T(0))
  140.                 p.printsign(str, p[i], i, i != p.Degree());
  141.             if (i == 0) break;
  142.         }
  143.         return str;
  144.     }
  145. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top