Advertisement
Guest User

Untitled

a guest
Oct 17th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define F(i, n) for(int i = 0; i < n; ++ i)
  6. #define int int64_t
  7.  
  8. string ToStr(int a) {
  9.     bool neg = false;
  10.     if(a < 0) {
  11.         neg = true;
  12.         a = -a;
  13.     }
  14.     string ans;
  15.     while(a) {
  16.         ans += char(a % 10 + '0');
  17.         a /= 10;
  18.     }
  19.     reverse(ans.begin(), ans.end());
  20.     return (neg ? "-" : "") + ans;
  21. }
  22.  
  23. class Complex {
  24. public:
  25.     Complex() {}
  26.     Complex(int re, int im) : re_(re), im_(im) {}
  27.  
  28.     int GetRe() const {
  29.         return re_;
  30.     }
  31.  
  32.     int GetIm() const {
  33.         return im_;
  34.     }
  35.  
  36.     Complex GetConjugate() const {
  37.         return Complex(re_, -im_);
  38.     }
  39.  
  40.     bool IsNull() const {
  41.         return (re_ == 0 && im_ == 0);
  42.     }
  43.  
  44.     bool IsOne() const {
  45.         return (re_ == 1 && im_ == 0);
  46.     }
  47.  
  48.     string ToString() {
  49.         if(!re_ && !im_) {
  50.             return "0";
  51.         }
  52.         if(re_ && im_) {
  53.             if(im_ == -1) {
  54.                 return ToStr(re_) + "-i";
  55.             }
  56.             if(im_ == 1) {
  57.                 return ToStr(re_) + "+i";
  58.             }
  59.             if(im_ < 0) {
  60.                 return ToStr(re_) + ToStr(im_) + 'i';
  61.             } else {
  62.                 return ToStr(re_) + '+' + ToStr(im_) + 'i';
  63.             }
  64.         }
  65.         if(!re_ && im_) {
  66.             if(im_ == -1) {
  67.                 return "-i";
  68.             }
  69.             if(im_ == 1) {
  70.                 return "i";
  71.             }
  72.             return ToStr(im_) + 'i';
  73.         }
  74.         if(re_ && !im_) {
  75.             return ToStr(re_);
  76.         }
  77.     }
  78.  
  79.     Complex operator+(const Complex& other) const {
  80.         return Complex(re_ + other.GetRe(), im_ + other.GetIm());
  81.     }
  82.  
  83.     Complex operator*(const int C) const {
  84.         return Complex(re_ * C, im_ * C);
  85.     }
  86.  
  87.     Complex operator*(const Complex& other) const {
  88.         return Complex(re_ * other.GetRe() - im_ * other.GetIm(),
  89.                        re_ * other.GetIm() + im_ * other.GetRe());
  90.     }
  91.  
  92.     bool CavDivide(const Complex& other) const {
  93.         Complex ans = *this * other.GetConjugate();
  94.         int dv = other.re_ * other.re_ + other.im_ * other.im_;
  95.         if(ans.re_ % dv) return false;
  96.         if(ans.im_ % dv) return false;
  97.         return true;
  98.     }
  99.  
  100.     Complex operator/(const Complex& other) const {
  101.         Complex ans = *this * other.GetConjugate();
  102.         int dv = other.re_ * other.re_ + other.im_ * other.im_;
  103.         return Complex(ans.re_ / dv, ans.im_ / dv);
  104.     }
  105.  
  106.     bool operator<(const Complex& other) const {
  107.         if (re_ < other.GetRe()) {
  108.             return true;
  109.         }
  110.         if (re_ > other.GetRe()) {
  111.             return false;
  112.         }
  113.         return (im_ < other.GetIm());
  114.     }
  115. private:
  116.     int re_, im_;
  117. };
  118.  
  119. class Polynomial {
  120. public:
  121.     Polynomial(const vector<int>& v) : v_(v), sz_(v.size()) {}
  122.  
  123.     Complex calc(const Complex& x) const {
  124.         Complex lst = Complex(v_[0], 0);
  125.         for (int i = 1; i < sz_; ++ i) {
  126.             lst = x * lst + Complex(v_[i], 0);
  127.         }
  128.         return lst;
  129.     }
  130. private:
  131.     int sz_;
  132.     vector<int> v_;
  133. };
  134.  
  135. const int kReDelta = 1e3 + 7, kImDelta = 1e3 + 7;
  136.  
  137. int32_t main() {
  138.     ios_base::sync_with_stdio(false);
  139.     int n; cin >> n; ++ n;
  140.     vector<int> v(n);
  141.     F(i, n) cin >> v[i];
  142.     set<Complex> ans;
  143.     while(v[0] == 0) {
  144.         ans.insert(Complex(0, 0));
  145.         vector<int> d;
  146.         for(int i = 1; i < v.size(); ++ i) d.push_back(v[i]);
  147.         v = d;
  148.     }
  149.     n = v.size();
  150.     reverse(v.begin(), v.end());
  151.     Polynomial pol(v);
  152.     Complex u = Complex(v[v.size() - 1], 0);
  153.     for (int re = -kReDelta; re <= kReDelta; ++ re) {
  154.         for (int im = -kImDelta; im <= kImDelta; ++ im) {
  155.             Complex cur = Complex(re, im);
  156.             Complex com = pol.calc(cur);
  157.             if (com.IsNull()) {
  158.                 ans.insert(cur);
  159.             }
  160.             Complex dv = cur * Complex(v[0], 0);
  161.             if(cur.IsNull()) continue;
  162.             if(!u.CavDivide(cur)) continue;
  163.             Complex cur2 = u / cur;
  164.             Complex com2 = pol.calc(cur2);
  165.             if (com2.IsNull()) {
  166.                 ans.insert(cur2);
  167.             }
  168.         }
  169.     }
  170.  
  171.  
  172.     /*for (auto com : ans) {
  173.         //cout << "idx" << idx << ' ' << u.ToString() << ' ' << ans[idx].ToString() << endl;
  174.         if(com.IsNull()) continue;
  175.         if (!u.CavDivide(com)) {
  176.             u = Complex(1, 0);
  177.             break;
  178.         }
  179.         u = u / com;
  180.     }
  181.     if (pol.calc(u).IsNull()) ans.insert(u);
  182.     Complex oth = Complex(-u.GetRe(), -u.GetIm());
  183.     if (pol.calc(oth).IsNull()) ans.insert(oth);*/
  184.  
  185.     cout << ans.size() << endl;
  186.     for(auto com : ans) {
  187.         cout << com.ToString() << ' ';
  188.     }
  189. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement