#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template static void amin(T &x, U y) { if (y < x) x = y; } template static void amax(T &x, U y) { if (x < y) x = y; } struct GModInt { static int Mod; unsigned x; GModInt() : x(0) { } GModInt(signed sig) { int sigt = sig % Mod; if (sigt < 0) sigt += Mod; x = sigt; } GModInt(signed long long sig) { int sigt = sig % Mod; if (sigt < 0) sigt += Mod; x = sigt; } int get() const { return (int)x; } GModInt &operator+=(GModInt that) { if ((x += that.x) >= (unsigned)Mod) x -= Mod; return *this; } GModInt &operator-=(GModInt that) { if ((x += Mod - that.x) >= (unsigned)Mod) x -= Mod; return *this; } GModInt &operator*=(GModInt that) { x = (unsigned long long)x * that.x % Mod; return *this; } GModInt &operator/=(GModInt that) { return *this *= that.inverse(); } GModInt operator+(GModInt that) const { return GModInt(*this) += that; } GModInt operator-(GModInt that) const { return GModInt(*this) -= that; } GModInt operator*(GModInt that) const { return GModInt(*this) *= that; } GModInt operator/(GModInt that) const { return GModInt(*this) /= that; } //Modと素であることが保証されるかどうか確認すること! GModInt inverse() const { signed a = x, b = Mod, u = 1, v = 0; while (b) { signed t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); } if (u < 0) u += Mod; GModInt res; res.x = (unsigned)u; return res; } bool operator==(GModInt that) const { return x == that.x; } bool operator!=(GModInt that) const { return x != that.x; } GModInt operator-() const { GModInt t; t.x = x == 0 ? 0 : Mod - x; return t; } }; int GModInt::Mod = 0; typedef GModInt mint; mint operator^(mint a, unsigned long long k) { mint r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; } struct Polynomial { typedef mint Coef; typedef Coef Val; vector coef; //... + coef[2] x^2 + coef[1] x + coef[0] Polynomial() {} explicit Polynomial(int n) : coef(n) {} static Polynomial One() { Polynomial r(1); r.coef[0] = 1; return r; } static Polynomial X() { Polynomial r(2); r.coef[1] = 1; return r; } bool iszero() const { return coef.empty(); } int degree1() const { return coef.size(); } //degree + 1 int resize(int d) { if (degree1() < d) coef.resize(d); return d; } const Coef operator[](int i) const { return i >= degree1() ? Coef() : coef[i]; } void canonicalize() { int i = coef.size(); while (i > 0 && coef[i - 1] == Coef()) i --; coef.resize(i); } Val evalute(Val x) const { int d = degree1(); Val t = 0, y = 1; rep(i, d) { t += y * coef[i]; y *= x; } return t; } Polynomial &operator+=(const Polynomial &that) { int d = resize(that.degree1()); for (int i = 0; i < d; i ++) coef[i] += that[i]; canonicalize(); return *this; } Polynomial operator+(const Polynomial &that) const { return Polynomial(*this) += that; } Polynomial &operator-=(const Polynomial &that) { int d = resize(that.degree1()); for (int i = 0; i < d; i ++) coef[i] -= that[i]; canonicalize(); return *this; } Polynomial operator-(const Polynomial &that) const { return Polynomial(*this) -= that; } Polynomial operator-() const { int d = degree1(); Polynomial res(d); for (int i = 0; i < d; i ++) res.coef[i] = - coef[i]; return res; } //naive Polynomial operator*(const Polynomial &that) const { if (iszero() || that.iszero()) return Polynomial(); int x = degree1(), y = that.degree1(), d = x + y - 1; Polynomial res(d); rep(i, x) rep(j, y) res.coef[i + j] += coef[i] * that.coef[j]; res.canonicalize(); return res; } //long division pair divmod(const Polynomial &that) const { int x = degree1() - 1, y = that.degree1() - 1; int d = max(0, x - y); Polynomial q(d + 1), r = *this; for (int i = x; i >= y; i --) { Coef t = r.coef[i] / that.coef[y]; q.coef[i - y] = t; assert(t * that.coef[y] == r.coef[i]); r.coef[i] = 0; if (t == 0) continue; for (int j = 0; j < y; j ++) r.coef[i - y + j] -= t * that.coef[j]; } q.canonicalize(); r.canonicalize(); return make_pair(q, r); } Polynomial operator/(const Polynomial &that) const { return divmod(that).first; } Polynomial operator%(const Polynomial &that) const { return divmod(that).second; } Polynomial divideByLC() const { if (degree1() == 0) return *this; Polynomial res(degree1()); auto inv = coef[coef.size() - 1].inverse(); rep(i, coef.size()) res.coef[i] = coef[i] * inv; return res; } }; Polynomial gcd(const Polynomial &x, const Polynomial &y) { if (y.iszero()) { return x.divideByLC(); } else { return gcd(y, x % y); } } Polynomial powmod(Polynomial a, long long k, const Polynomial &mod) { Polynomial r = Polynomial::One(); while (k != 0) { if (k & 1) r = r * a % mod; a = a * a % mod; k >>= 1; } return r; } struct RandomModInt { default_random_engine re; uniform_int_distribution dist; #ifndef _DEBUG RandomModInt() : re(random_device{}()), dist(1, mint::Mod - 1) { } #else RandomModInt() : re(), dist(1, mint::Mod - 1) { } #endif mint operator()() { mint r; r.x = dist(re); return r; } }; Polynomial equalDegreeSplitting(const Polynomial &f, int d, RandomModInt &randomModInt) { int n = (int)f.degree1() - 1; assert(0 < d && d < n && n % d == 0); assert(f.coef[n].get() == 1); while (1) { Polynomial a; rep(i, n) a.coef.push_back(randomModInt()); a.canonicalize(); if (a.degree1() <= 1) continue; auto g1 = gcd(a, f); if (1 < g1.degree1()) return g1; //b = a^((q^d-1)/2) mod f auto digit = powmod(a, (mint::Mod - 1) / 2, f); auto b = Polynomial::One(); for (int i = 0; i < d; ++ i) { if(i != 0) b = powmod(b, mint::Mod, f); b = b * digit % f; } auto g2 = gcd(b - Polynomial::One(), f); if (1 < g2.degree1() && g2.degree1() < f.degree1()) return g2; } } void equalDegreeFactorization(const Polynomial &f, int d, RandomModInt &randomModInt, vector &factors) { int n = (int)f.degree1() - 1; if (n == d) { factors.push_back(f); return; } auto g = equalDegreeSplitting(f, d, randomModInt); equalDegreeFactorization(g, d, randomModInt, factors); equalDegreeFactorization(f / g, d, randomModInt, factors); } void polynomialFactorizationOverFiniteField(Polynomial f, RandomModInt &randomModInt, vector> &factors) { f.canonicalize(); assert(0 < f.degree1() && f.coef[f.degree1() - 1].get() == 1); if (f.degree1() == 1) { factors.emplace_back(f, 1); return; } auto h = Polynomial::X(); auto v = f; int i = 0; while (1 < v.degree1()) { ++ i; h = powmod(h, mint::Mod, f); auto g = gcd(h - Polynomial::X(), v); if (1 < g.degree1()) { vector ts; equalDegreeFactorization(g, i, randomModInt, ts); for (auto &&t : ts) { int e = 0; do { ++ e; v = v / t; } while ((v % t).iszero()); factors.emplace_back(t, e); } } } } int main() { long long A; long long B; long long C; while (~scanf("%lld%lld%lld", &A, &B, &C)) { mint::Mod = 2000000011; RandomModInt randomModInt; Polynomial poly(4); poly.coef[0] = C; poly.coef[1] = B; poly.coef[2] = A; poly.coef[3] = 1; vector> factors; polynomialFactorizationOverFiniteField(poly, randomModInt, factors); vector ans; for (auto &&t : factors) { if (t.first.degree1() == 2) { int x = (mint() - t.first.coef[0]).get(); ans.push_back(x < mint::Mod / 2 ? x : -(mint::Mod - x)); } } sort(ans.begin(), ans.end()); if (ans.empty()) { puts("-1"); } else { for (int i = 0; i < (int)ans.size(); ++ i) { if (i != 0) putchar(' '); printf("%d", ans[i]); } puts(""); } } return 0; }