C. Pythagorean Triples

Codeforces

IDCF707C

Time1000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

Katya studies in a fifth grade. Recently her class studied right triangles and the Pythagorean theorem. It appeared, that there are triples of positive integers such that you can construct a right triangle with segments of lengths corresponding to triple. Such triples are called _Pythagorean triples_. For example, triples (3, 4, 5), (5, 12, 13) and (6, 8, 10) are Pythagorean triples. Here Katya wondered if she can specify the length of some side of right triangle and find any Pythagorean triple corresponding to such length? Note that the side which length is specified can be a cathetus as well as hypotenuse. Katya had no problems with completing this task. Will you do the same? ## Input The only line of the input contains single integer _n_ (1 ≤ _n_ ≤ 109) — the length of some side of a right triangle. ## Output Print two integers _m_ and _k_ (1 ≤ _m_, _k_ ≤ 1018), such that _n_, _m_ and _k_ form a Pythagorean triple, in the only line. In case if there is no any Pythagorean triple containing integer _n_, print - 1 in the only line. If there are many answers, print any of them. [samples] ## Note <center>![image](https://espresso.codeforces.com/dbf52eca60c009fe6de5fd0bbce69fbd861fd8e9.png)Illustration for the first sample. </center>

Katya 在上五年级。最近她的班级学习了直角三角形和勾股定理。他们发现，存在一些正整数三元组，使得可以用对应长度的线段构成一个直角三角形。这样的三元组被称为 _勾股三元组_。例如，三元组 #cf_span[(3, 4, 5)]、#cf_span[(5, 12, 13)] 和 #cf_span[(6, 8, 10)] 都是勾股三元组。此时 Katya 想知道，如果她指定了直角三角形某条边的长度，是否能找出一个包含该长度的勾股三元组？注意，指定长度的边可以是直角边，也可以是斜边。 Katya 很快完成了这个任务。你也能做到吗？输入仅一行，包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^9]）——直角三角形某条边的长度。请在一行中输出两个整数 #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ m, k ≤ 10^18]），使得 #cf_span[n]、#cf_span[m] 和 #cf_span[k] 构成一个勾股三元组。如果不存在包含整数 #cf_span[n] 的勾股三元组，请在一行中输出 #cf_span[-1]。如果存在多个答案，输出任意一个即可。第一个样例的图示。 ## Input 输入仅一行，包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^9]）——直角三角形某条边的长度。 ## Output 请在一行中输出两个整数 #cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ m, k ≤ 10^18]），使得 #cf_span[n]、#cf_span[m] 和 #cf_span[k] 构成一个勾股三元组。如果不存在包含整数 #cf_span[n] 的勾股三元组，请在一行中输出 #cf_span[-1]。如果存在多个答案，输出任意一个即可。 [samples] ## Note 第一个样例的图示。

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^9 $. **Objective** Find integers $ m, k \in \mathbb{Z}^+ $ with $ 1 \leq m, k \leq 10^{18} $ such that $ \{n, m, k\} $ form a Pythagorean triple, i.e., $$ n^2 + m^2 = k^2 \quad \text{or} \quad n^2 + k^2 = m^2 \quad \text{or} \quad m^2 + k^2 = n^2. $$ If no such $ m, k $ exist, output $-1$.

Samples

Input #1

Output #1

4 5

Input #2

Output #2

8 10

Input #3

Output #3

\-1

Input #4

Output #4

144 145

Input #5

Output #5

2244 2245

API Response (JSON)

{
  "problem": {
    "name": "C. Pythagorean Triples",
    "description": {
      "content": "Katya studies in a fifth grade. Recently her class studied right triangles and the Pythagorean theorem. It appeared, that there are triples of positive integers such that you can construct a right tri",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF707C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Katya studies in a fifth grade. Recently her class studied right triangles and the Pythagorean theorem. It appeared, that there are triples of positive integers such that you can construct a right tri...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Katya 在上五年级。最近她的班级学习了直角三角形和勾股定理。他们发现，存在一些正整数三元组，使得可以用对应长度的线段构成一个直角三角形。这样的三元组被称为 _勾股三元组_。\n\n例如，三元组 #cf_span[(3, 4, 5)]、#cf_span[(5, 12, 13)] 和 #cf_span[(6, 8, 10)] 都是勾股三元组。\n\n此时 Katya 想知道，如果她指定了直角三角形某条边的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10^9 $.  \n\n**Objective**  \nFind integers $ m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq m, k \\leq 10^{18} $ such that $ \\{n, m, k\\} $ form a ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments