O(1) approach to solve Codeforces Round 368 (Div. 2) Problem C
source link: https://codeforces.com/blog/entry/116504
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Problem — 707C - Pythagorean Triples
Let's consider a triangle with sides n, m, and k.
According to the Pythagorean Theorem, we know that n² + m² = k².
By rearranging the equation, we have k² — m² = n².
Further simplifying, we find that (k + m)(k — m) = n².
n² can be represented as n²*1.
Therefore, we can assume that k + m = n² and k — m = 1
By adding and subtracting these equations, we obtain k = (n² + 1)/2 and m = (n² — 1)/2.
This solution is valid when n is an odd number since we assume k — m = 1.
So, how to handle the case when n is even?
To handle even values, we can observe the following pattern: If (k — m) is odd, the solution is applicable to odd values of n. Conversely, if (k — m) is even, the solution is applicable to even values of n.
Set k = (n^2 + 2n) / 4 Set m = (n^2 — 2n) / 4
From this we get, k = (n*n-1)/4 and m = (n*n)/4)+1
Link to My Solution : 206019093
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK