193. Quadratic Equation Factoring

Codeforces

IDCF10269193

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You're given a quadratic equation, in the form of $y = a x^2 + b x + c$. Your task is to find all possible factorizations of this quadratic equation, using only positive integers. In other words, you have to find all pairs of binomials $c x + d$, where $c$ and $c$ are both positive integers, such that the product of the two binomials is the original quadratic equation. Sort the factorizations in ASCII order (you can use your language's built-in sorting method). The only line of input contains three space-separated *positive* integers $a$, $b$, and $c$: the coefficient on the $x$ term of the quadratic equation, and the constant term of the quadratic equation, respectively. Output all of the integer factorizations of the given quadratic equation, each on a new line. Each one should be in the format $(x + c 1) (x + c 2)$. If there are no possible factorizations, output "-1" (no quotes). ## Input The only line of input contains three space-separated *positive* integers $a$, $b$, and $c$: the coefficient on the $x$ term of the quadratic equation, and the constant term of the quadratic equation, respectively. ## Output Output all of the integer factorizations of the given quadratic equation, each on a new line. Each one should be in the format $(x + c 1) (x + c 2)$.If there are no possible factorizations, output "-1" (no quotes). [samples]

**Definitions** Let $ a, b, c \in \mathbb{Z}^+ $ be the coefficients of the quadratic $ y = ax^2 + bx + c $. **Constraints** $ a, b, c \geq 1 $ **Objective** Find all pairs of positive integers $ (d, e) $ such that: $$ ax^2 + bx + c = (px + q)(rx + s) $$ where $ p, q, r, s \in \mathbb{Z}^+ $, $ pr = a $, $ qs = c $, and $ ps + qr = b $. For each valid factorization, output in the form $ (x + q)(x + s) $ **only if** $ p = r = 1 $. If no such factorization exists with $ p = r = 1 $, output "-1". Sort all valid outputs in ASCII order.

API Response (JSON)

{
  "problem": {
    "name": "193. Quadratic Equation Factoring",
    "description": {
      "content": "You're given a quadratic equation, in the form of $y = a x^2 + b x + c$. Your task is to find all possible factorizations of this quadratic equation, using only positive integers. In other words, you ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269193"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're given a quadratic equation, in the form of $y = a x^2 + b x + c$. Your task is to find all possible factorizations of this quadratic equation, using only positive integers. In other words, you ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b, c \\in \\mathbb{Z}^+ $ be the coefficients of the quadratic $ y = ax^2 + bx + c $.  \n\n**Constraints**  \n$ a, b, c \\geq 1 $  \n\n**Objective**  \nFind all pairs of positive int...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments