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 .
This task is finding pair of positive integer (a, b) that satisfies a2 + b2 = c2 for given integer c.
and judge whether it is an integer. It takes O(c·f(c)) if f(c) is time complexity of sqrt function.
Approach 1: You can brute-force a because 1 ≤ c ≤ 500000.
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.
In this blog the constraints is 1 ≤ c ≤ 500000, so I commented these solutions.