Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define F(i, n) for(int i = 0; i < n; ++ i)
- #define int int64_t
- string ToStr(int a) {
- bool neg = false;
- if(a < 0) {
- neg = true;
- a = -a;
- }
- string ans;
- while(a) {
- ans += char(a % 10 + '0');
- a /= 10;
- }
- reverse(ans.begin(), ans.end());
- return (neg ? "-" : "") + ans;
- }
- class Complex {
- public:
- Complex() {}
- Complex(int re, int im) : re_(re), im_(im) {}
- int GetRe() const {
- return re_;
- }
- int GetIm() const {
- return im_;
- }
- Complex GetConjugate() const {
- return Complex(re_, -im_);
- }
- bool IsNull() const {
- return (re_ == 0 && im_ == 0);
- }
- bool IsOne() const {
- return (re_ == 1 && im_ == 0);
- }
- string ToString() {
- if(!re_ && !im_) {
- return "0";
- }
- if(re_ && im_) {
- if(im_ == -1) {
- return ToStr(re_) + "-i";
- }
- if(im_ == 1) {
- return ToStr(re_) + "+i";
- }
- if(im_ < 0) {
- return ToStr(re_) + ToStr(im_) + 'i';
- } else {
- return ToStr(re_) + '+' + ToStr(im_) + 'i';
- }
- }
- if(!re_ && im_) {
- if(im_ == -1) {
- return "-i";
- }
- if(im_ == 1) {
- return "i";
- }
- return ToStr(im_) + 'i';
- }
- if(re_ && !im_) {
- return ToStr(re_);
- }
- }
- Complex operator+(const Complex& other) const {
- return Complex(re_ + other.GetRe(), im_ + other.GetIm());
- }
- Complex operator*(const int C) const {
- return Complex(re_ * C, im_ * C);
- }
- Complex operator*(const Complex& other) const {
- return Complex(re_ * other.GetRe() - im_ * other.GetIm(),
- re_ * other.GetIm() + im_ * other.GetRe());
- }
- bool CavDivide(const Complex& other) const {
- Complex ans = *this * other.GetConjugate();
- int dv = other.re_ * other.re_ + other.im_ * other.im_;
- if(ans.re_ % dv) return false;
- if(ans.im_ % dv) return false;
- return true;
- }
- Complex operator/(const Complex& other) const {
- Complex ans = *this * other.GetConjugate();
- int dv = other.re_ * other.re_ + other.im_ * other.im_;
- return Complex(ans.re_ / dv, ans.im_ / dv);
- }
- bool operator<(const Complex& other) const {
- if (re_ < other.GetRe()) {
- return true;
- }
- if (re_ > other.GetRe()) {
- return false;
- }
- return (im_ < other.GetIm());
- }
- private:
- int re_, im_;
- };
- class Polynomial {
- public:
- Polynomial(const vector<int>& v) : v_(v), sz_(v.size()) {}
- Complex calc(const Complex& x) const {
- Complex lst = Complex(v_[0], 0);
- for (int i = 1; i < sz_; ++ i) {
- lst = x * lst + Complex(v_[i], 0);
- }
- return lst;
- }
- private:
- int sz_;
- vector<int> v_;
- };
- const int kReDelta = 1e3 + 7, kImDelta = 1e3 + 7;
- int32_t main() {
- ios_base::sync_with_stdio(false);
- int n; cin >> n; ++ n;
- vector<int> v(n);
- F(i, n) cin >> v[i];
- set<Complex> ans;
- while(v[0] == 0) {
- ans.insert(Complex(0, 0));
- vector<int> d;
- for(int i = 1; i < v.size(); ++ i) d.push_back(v[i]);
- v = d;
- }
- n = v.size();
- reverse(v.begin(), v.end());
- Polynomial pol(v);
- Complex u = Complex(v[v.size() - 1], 0);
- for (int re = -kReDelta; re <= kReDelta; ++ re) {
- for (int im = -kImDelta; im <= kImDelta; ++ im) {
- Complex cur = Complex(re, im);
- Complex com = pol.calc(cur);
- if (com.IsNull()) {
- ans.insert(cur);
- }
- Complex dv = cur * Complex(v[0], 0);
- if(cur.IsNull()) continue;
- if(!u.CavDivide(cur)) continue;
- Complex cur2 = u / cur;
- Complex com2 = pol.calc(cur2);
- if (com2.IsNull()) {
- ans.insert(cur2);
- }
- }
- }
- /*for (auto com : ans) {
- //cout << "idx" << idx << ' ' << u.ToString() << ' ' << ans[idx].ToString() << endl;
- if(com.IsNull()) continue;
- if (!u.CavDivide(com)) {
- u = Complex(1, 0);
- break;
- }
- u = u / com;
- }
- if (pol.calc(u).IsNull()) ans.insert(u);
- Complex oth = Complex(-u.GetRe(), -u.GetIm());
- if (pol.calc(oth).IsNull()) ans.insert(oth);*/
- cout << ans.size() << endl;
- for(auto com : ans) {
- cout << com.ToString() << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement