daihan's blog

Pythagorian triple
By daihan, 8 years ago, In English

I have found a problem about pythagorian triple . But input , output will be as like bellow :

Input

Each case will contain one positive integer c (1 ≤ c ≤ 500,000), the length of the hypotenuse of the right triangle.

Output

For each case, print the case number first, then print the other two sides a and b ( a and b are cathetus ). If no such a, b can be found which satisfies the above condition print “Impossible” without quotes. If there are multiple pair of (a, b) exists, print the one with smallest possible a .

5

Case #1: 3 4

6

Case #2: Impossible

25

Case #3: 7 24

How to solve this problem ? CF has a problem : http://codeforces.net/problemset/problem/707/C . But most of the solution are assumed C as cathetus . How to solve if we assume C as hypotenuse .

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This task is finding pair of positive integer (a, b) that satisfies a2 + b2 = c2 for given integer c.

Approach 1: You can brute-force a because 1 ≤ c ≤ 500000. and judge whether it is an integer. It takes O(c·f(c)) if f(c) is time complexity of sqrt function.

Code

Approach 2: You can do two-pointer technique for a and b like this code, and it takes O(c). It is ok for c ≤ 108.

Code

In this blog the constraints is 1 ≤ c ≤ 500000, so I commented these solutions.

→ Reply