Advertisement
Guest User

Untitled

a guest
Oct 17th, 2019
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.42 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.  
  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. }
  161. }
  162. Complex u = Complex(v[v.size() - 1], 0) / Complex(v[0], 0);
  163. for (auto com : ans) {
  164. //cout << "idx" << idx << ' ' << u.ToString() << ' ' << ans[idx].ToString() << endl;
  165. if (!u.CavDivide(com)) {
  166. u = Complex(1, 0);
  167. break;
  168. }
  169. u = u / com;
  170. }
  171. if (pol.calc(u).IsNull()) ans.insert(u);
  172. Complex oth = Complex(-u.GetRe(), -u.GetIm());
  173. if (pol.calc(oth).IsNull()) ans.insert(oth);
  174.  
  175. cout << ans.size() << endl;
  176. for(auto com : ans) {
  177. cout << com.ToString() << ' ';
  178. }
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement